【HDU 3518】Boring counting

题目传送门:http://acm.hdu.edu.cn/showproblem.php?pid=3518
数据生成器:http://paste.ubuntu.com/18021072/

这个,我是SA乱搞,时间复杂度O(n^3)QAQ,不过要把我卡到这个时间复杂度的数据貌似不好出
还是说说正解吧:枚举长度,然后height[]数组分组搞一搞,又是论文题QAQ
其实最开始想的是SAM,每个节点记录一个最先出现的位置和最后出现的位置,而且这样的话,貌似可以做到O(n)
但是懒得写啦! 还是上一个SA的乱搞代码就水过了吧!

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

const int MAXN = 3000+9;

char pat[MAXN]; int n;

namespace Suffix_Array{
	#define SA Suffix_Array
	#define SIGMA_SIZE 26
	int sa[MAXN],bot[MAXN],*tmp,*rank;
	int t1[MAXN],t2[MAXN],height[MAXN],m;
	
	inline void GetHeight(){
		for (int i=1,t,p1,p2;i<=n;i++)if(rank[i]>1){
			t = max(0,height[rank[i-1]]-1);
			p1 = i+t; p2 = sa[rank[i]-1]+t;
			while (pat[p1++]==pat[p2++]) t++;
			height[rank[i]] = t;
		}
	}
	
	inline void build(){
		memset(sa,0,sizeof(sa));
		memset(t1,0,sizeof(t1));
		memset(t2,0,sizeof(t2));
		memset(height,0,sizeof(height));
		memset(bot,0,sizeof(bot));
		
		tmp = t1; rank = t2;
		n = strlen(pat+1); m = SIGMA_SIZE;
		for (int i=1;i<=n;i++) bot[tmp[i]=pat[i]-'a'+1]++;
		for (int i=2;i<=m;i++) bot[i] += bot[i-1];
		for (int i=1;i<=n;i++) sa[bot[tmp[i]]--] = i;
		m = rank[sa[1]] = 1;
		for (int i=2;i<=n;i++)
			rank[sa[i]] = (tmp[sa[i]]==tmp[sa[i-1]])?m:++m;
		
		for (int k=1;k<=n;k*=2){int T=0;
			for (int i=n-k+1;i<=n;i++) tmp[++T] = i;
			for (int i=1;i<=n;i++) if (sa[i] > k) tmp[++T] = sa[i]-k;
			for (int i=1;i<=m;i++) bot[i] = 0;
			for (int i=1;i<=n;i++) bot[rank[i]]++;
			for (int i=2;i<=m;i++) bot[i] += bot[i-1];
			for (int i=n;i;i--) sa[bot[rank[tmp[i]]]--] = tmp[i];
			
			swap(rank, tmp); m = rank[sa[1]] = 1;
			for (int i=2;i<=n;i++)
				if (tmp[sa[i]]==tmp[sa[i-1]] && tmp[sa[i]+k]==tmp[sa[i-1]+k]) rank[sa[i]]=m;
				else rank[sa[i]] = ++m;
			
			if (m >= n) break;
		}	
		GetHeight();
	}
	
	inline bool judge(int w, int len){
		int mn=sa[w]-len, mx=sa[w]+len;
		while (w < n && height[w+1]>=len) 
			if (sa[++w] <= mn || sa[w] >= mx) 
				return true;
		return false;
	}
	
	inline void solve(){
		int vout = 0;
		for (int i=1;i<=n;i++){
			int len=n-sa[i]-height[i]+1;
			for (int j=len;j;j--)
				if (judge(i,j+height[i]))
					{vout += j; break;}
		}
		printf("%d\n",vout);	
	}
};

int main(){
	while (~scanf("%s",pat+1) && pat[1] != '#'){
		SA::build();
		SA::solve();
	}
	return 0;
}

【BZOJ 1355】[Baltic2009]Radio Transmission

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=1355
离线版题目:http://paste.ubuntu.com/17890900/

这一道题目,让我有一种自杀的冲动QAQ
先是想:嗯,SA的话O(nlogn)应该能过,于是开开心心去写SA
然而都快写完了,突然发现:WTF!被卡内存了
于是想KMP,总算回忆起那个神奇的结论,于是又写KMP,结果还写挂啦QAQ
不说了,说的了都是泪QAQ
本来是一道水题,结果做了俩小时QAQ

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

const int MAXN = 2000000+9;

char pat[MAXN];
int nxt[MAXN],n;

int main(){
	scanf("%d%s",&n,pat+1);
	
	for (int i=2,j=0;i<=n;i++){
		while (j&&pat[j+1] != pat[i]) j=nxt[j];
		if (pat[j+1]==pat[i]) j++;
		nxt[i] = j; 
	}
	
	printf("%d\n",n-nxt[n]);
	
	return 0;
} 

好吧,我承认这题还是比较好玩的。以前以为Kmp的那个结论只有整除的时候才能用。
刚刚证了证发现非整除也可以用QAQ
另外%这位大神,用hash把内存给省下去了:http://blog.csdn.net/wzq_qwq/article/details/49005295
我hash果然还是弱得完全没法用

【Codeforces 100548G】The Problem to Slow Down You

题目传送门:http://codeforces.com/gym/100548 ps:是G题

首先,这个题目肯定可以用manacher配合SA/SAM来完成,然而SA/SAM的代码不好写QAQ
但是我们发现,需要的所有串都是回文串,所以可以建两个PAM,然后一起跑DFS
1A 撒花! *★,°*:.☆\( ̄▽ ̄)/$:*.°★*

#include<iostream>
#include<cstdio>
#include<cstring>
#define LL long long
using namespace std;

const int MAXN = 200000+9;
const int SIGMA_SIZE = 26;

struct Palindromic_Tree{
	#define PAM Palindromic_Tree
	int ch[MAXN][SIGMA_SIZE],fail[MAXN];
	int cnt,last,n,sz[MAXN],len[MAXN];
	char *pat; LL ret;
	
	inline int newnode(){
		cnt += 1;
		memset(ch[cnt],0,sizeof(ch[cnt]));
		fail[cnt] = sz[cnt] = len[cnt] = 0;
		return cnt;
	}
	
	inline void init(){
		cnt = last = 1; 
		fail[0] = fail[1] = 1;
		sz[0] = sz[1] = len[0] = 0; len[1] = -1;
		memset(ch[0],0,sizeof(ch[0]));
		memset(ch[1],0,sizeof(ch[1]));
	}
	
	inline void extend(int p, int c){
		int w = last;
		while (pat[p-len[w]-1] != pat[p]) w = fail[w];
		if (!ch[w]){
			int nw = newnode(),k=fail[w]; len[nw] = len[w]+2;
			while (pat[p-len[k]-1] != pat[p]) k = fail[k];
			fail[nw] = ch[k]; ch[w] = nw;
		}
		last = ch[w];
		sz[last]++;
	}
	
	inline void build(char *s){
		init(); pat = s;
		n = strlen(s+1);
		for (int i=1;i<=n;i++)
			extend(i,s[i]-'a');
		for (int i=cnt;i;i--)
			sz[fail[i]] += sz[i];
	}
	
	void DFS(int pa, int pb, PAM *s){
		if (pa > 1 && pb > 1) ret += (LL)sz[pa]*(LL)s->sz[pb];
		for (int i=0;i<SIGMA_SIZE;i++)
			if (ch[pa][i] && s->ch[pb][i])
				DFS(ch[pa][i],s->ch[pb][i],s);
	}
	
	inline LL solve(PAM *a){
		ret = 0LL;
		DFS(0,0,a);
		DFS(1,1,a);
		return ret;
	}
}A,B;

char sa[MAXN],sb[MAXN];

int main(){
	int T,TT=0; cin>>T;
	while (T--){
		scanf("%s%s",sa+1,sb+1);
		A.build(sa); B.build(sb);	
		printf("Case #%d: %I64d\n",++TT,A.solve(&B));
	}
	return 0;
}