템 플 릿 복습 계획 - 문자열

http://uoj.ac/problem/35 접미사 배열 템 플 릿 은 천고 신 번 jxr, 매크로 개선 판 에서 왔 습 니 다.

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define rep(i,l,r) for(int i=l;i<=r;i++)
#define per(i,r,l) for(int i=r;i>=1;i--)
#define equ(x) (y[sa[i]+x]==y[sa[i-1]+x])
const int N=100000+5;
int a[N],b[N],c[N],*x,*y,sa[N],rk[N],h[N],n;
char s[N];
void radix(int m){
	rep(i,1,m)c[i]=0;
	rep(i,1,n)c[x[y[i]]]++;
	rep(i,1,m)c[i]+=c[i-1];
	per(i,n,1)sa[c[x[y[i]]]--]=y[i];
}
void build(int m){
	rep(i,1,n)x[i]=s[i],y[i]=i;radix(m);
	for(int k=1,p=0;k<=n;k<<=1,m=p,p=0){
		rep(i,n-k+1,n)y[++p]=i;
		rep(i,1,n)if(sa[i]>k)y[++p]=sa[i]-k;
		radix(m);swap(x,y);x[sa[1]]=p=1;
		rep(i,2,n)x[sa[i]]=equ(0)&&equ(k)?p:++p;
		if(p==n)break;
	}
	rep(i,1,n)rk[sa[i]]=i;
	for(int i=1,k=0;i<=n;h[rk[i++]]=k)
	for(k?k--:0;i+k<=n&&s[i+k]==s[sa[rk[i]-1]+k];k++);
}
int main(){
	//freopen("a.in","r",stdin);
	scanf("%s",s+1);n=strlen(s+1);
	x=a;y=b;build(200);
	rep(i,1,n)printf("%d ",sa[i]);putchar('
');
	rep(i,2,n)printf("%d ",h[i]);putchar('
');
	return 0;
}

http://codevs.cn/problem/1204/ KMP (이 건 복습 안 해도 될 것 같은 데...)

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define rep(i,l,r) for(int i=l;i<=r;i++)
const int N=100+5;
char s[N],t[N];
int n,m,fail[N];
void getfail(){
	int j=0;
	rep(i,2,m){
		while(j&&t[j+1]!=t[i])j=fail[j];
		j+=t[j+1]==t[i];
		fail[i]=j;
	}
}
int kmp(){
	int j=0;
	rep(i,1,n){
		while(j&&t[j+1]!=s[i])j=fail[j];
		j+=t[j+1]==s[i];
		if(j==m)return i-m+1;
	}
}
int main(){
	//freopen("a.in","r",stdin);
	scanf("%s%s",s+1,t+1);n=strlen(s+1);m=strlen(t+1);
	getfail();printf("%d
",kmp());
	return 0;
}

http://acm.hdu.edu.cn/showproblem.php?pid=3068 manacher.

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=110000+5;
const int M=220000+5;
#define rep(i,l,r) for(int i=l;i<=r;i++)
char s[N],t[M];
int n,m,p[M];
void build(){
	for(int i=1;i<=n;i++)
	t[i<<1]=s[i],t[i*2-1]='#';
	t[m=2*n+1]='#';
}
void manacher(){
	int mx=0,id=0;
	rep(i,1,m){
		if(mx>i)p[i]=min(p[2*id-i],mx-i);
		else p[i]=1;
		while(i-p[i]>=1&&i+p[i]<=m&&t[i-p[i]]==t[i+p[i]])p[i]++;
		if(i+p[i]>mx)mx=i+p[i],id=i;
	}
}
int main(){
	//freopen("a.in","r",stdin);
	while(~scanf("%s",s+1)){
		n=strlen(s+1);
		build();
		manacher();
		int ans=0;
		rep(i,1,m)ans=max(ans,p[i]);
		printf("%d
",ans-1);
	}
	return 0;
}

http://uoj.ac/problem/103 회문수

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define rep(i,l,r) for(int i=l;i<=r;i++)
#define per(i,r,l) for(int i=r;i>=l;i--)
typedef long long ll;
const int N=300000+5;
int len[N],suf[N],ch[N][26],sum[N];
int node,last;
void init(){
	len[suf[suf[2]=1]=1]=-1;
	node=last=2;
}
char s[N];
bool add(int i){
	int cur=last,c=s[i]-'a';
	while(s[i-len[cur]-1]!=s[i])cur=suf[cur];
	bool flag=true;
	if(!ch[cur][c]){
		len[last=++node]=len[cur]+2;ch[cur][c]=last;
		int tmp=suf[cur];
		while(s[i-len[tmp]-1]!=s[i])tmp=suf[tmp];
		suf[last]=len[last]==1?2:ch[tmp][c];
	}else flag=false;
	last=ch[cur][c];sum[last]++;
	return flag;
}
int main(){
	//freopen("a.in","r",stdin);
	scanf("%s",s+1);int n=strlen(s+1);
	init();
	rep(i,1,n)add(i);
	per(i,node,1)sum[suf[i]]+=sum[i];
	ll ans=0;
	rep(i,1,node)ans=max(ans,(ll)len[i]*sum[i]);
	printf("%lld
",ans);
	return 0;
}

http://acm.hdu.edu.cn/showproblem.php?pid=4622 접미사 자동 동기 (열 번 묵독... 접미사 자동 기 는 두 배의 공간 을 열 어야 합 니 다)

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=2000+5;
struct state{
	state *par,*go[26];
	int len;
	void clear(){
		par=0;len=0;
		memset(go,0,sizeof(go));
	}
	int calc(){
		if(!par)return 0;
		return len-par->len;
	}
}statepool[N<<1],*cur,*root,*last;
void init(){
	cur=statepool;
	last=root=cur++;
	root->clear();
}
int extend(int w){
	int ans=0;
	state *p=last,*np=cur++;
	np->clear();np->len=p->len+1;
	for(;p&&!p->go[w];p=p->par)p->go[w]=np;
	if(!p)np->par=root;
	else{
		state *q=p->go[w];
		if(q->len==p->len+1)np->par=q;
		else{
			state *nq=cur++;nq->clear();
			memcpy(nq->go,q->go,sizeof(q->go));
			nq->len=p->len+1;
			ans-=q->calc();
			nq->par=q->par;
			q->par=np->par=nq;
			ans+=q->calc()+nq->calc();
			for(;p&&p->go[w]==q;p=p->par)p->go[w]=nq;
		}
	}
	ans+=np->calc();
	last=np;
	return ans;
}
char s[N];
int table[N][N];
int main(){
	//freopen("a.in","r",stdin);
	int T;scanf("%d",&T);
	while(T--){
		scanf("%s",s+1);int n=strlen(s+1);
		for(int i=1;i<=n;i++){
			init();
			for(int j=i;j<=n;j++)
			table[i][j]=table[i][j-1]+extend(s[j]-'a');
		}
		int q;scanf("%d",&q);
		while(q--){
			int l,r;scanf("%d%d",&l,&r);
			printf("%d
",table[l][r]);
		}
	}
	return 0;
}

http://acm.hdu.edu.cn/showproblem.php?pid=2222  이것 도 복습 시리즈 의 AC 자동 동기 로 (제목 에 구덩이 가 있다)

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
struct Node{
	int fail,ch[26],cnt;
	void clear(){
		memset(ch,0,sizeof(ch));
		fail=cnt=0;
	}
}tr[500005];
int sz;
void init(){
	tr[sz=0].clear();
}
void insert(char *s,int k){
	int u;
	for(u=0;*s;s++){
		int c=*s-'a';
		if(!tr[u].ch[c]){
			tr[u].ch[c]=++sz;
			tr[sz].clear();
		}
		u=tr[u].ch[c];
	}
	tr[u].cnt++;
}
bool ex[10005];
void bfs(){
	queue<int>q;q.push(0);
	while(!q.empty()){
		int u=q.front();q.pop();
		for(int i=0;i<26;i++)
		if(tr[u].ch[i]){
			int v=tr[u].ch[i];
			if(u)tr[v].fail=tr[tr[u].fail].ch[i];
			q.push(v);
		}else tr[u].ch[i]=tr[tr[u].fail].ch[i];
	}
}
int find(char *s){
	int ans=0;
	for(int u=0;*s;s++){
		int c=*s-'a';
		u=tr[u].ch[c];
		for(int p=u;p;p=tr[p].fail)
		if(tr[p].cnt>=0)ans+=tr[p].cnt,tr[p].cnt=-1;
		else break;
	}
	return ans;
}
char s[55],t[1000005];
int main(){
	//freopen("a.in","r",stdin);
	int T;scanf("%d",&T);
	while(T--){
		int n;scanf("%d",&n);
		init();
		for(int i=1;i<=n;i++){
			scanf("%s",s);
			insert(s,i);
			ex[i]=0;
		}
		bfs();
		scanf("%s",t);
		printf("%d
",find(t));
	}
	return 0;
}