字符串匹配

KMP

时间复杂度：\(O(n)\)

#define N 1000005
int nxt[N],m,n;
char a[N],b[N];
inline void get_nxt(){
    for(int i=2,j=0;i<=m;++i){
        while(j&&b[i]!=b[j+1]) j=nxt[j];
        if(b[i]==b[j+1]) ++j;
        nxt[i]=j;
    }
}
inline void kmp(){
    for(int i=1,j=0;i<=n;++i){
        while(j&&a[i]!=b[j+1]) j=nxt[j];
        if(a[i]==b[j+1]) ++j;
        if(j==m) printf("%d\n",i-m+1);
    }
}

扩展KMP

求一个串对于另一个串的每个后缀的LCP.
时间复杂度：\(O()\)

trie树

时间复杂度：\(O(\sum|S_i|)\)

#define N 100005
struct trie{
    int chl[26];bool b;
}tr[L];
int cnt;
inline void insert(char s[]){
    int u=0,l=strlen(s+1);
    for(int i=1;i<=l;++i){
        if(!tr[u].chl[s[i]-'a'])
            tr[u].chl[s[i]-'a']=++cnt;
        u=tr[u].chl[s[i]-'a'];
    }
    tr[u].b=true;
}
inline bool find_pre(char s[]){
    int u=0,l=strlen(s+1);
    for(int i=1;i<=l;++i){
        if(!tr[u].chl[s[i]-'a'])
            return false;
        u=tr[u].chl[s[i]-'a'];
    }
    return true;
}

AC自动机

#define N 105
#define T 10005
#define M 1350005
struct trie{
    int chl[26],nxt;bool b;
}tr[T];
int tot[T],cnt;
queue<int> q;
inline void insert(char s[]){
    int u=0,l=strlen(s+1);
    for(int i=1;i<=l;++i){
        if(!tr[u].chl[s[i]-'a'])
            tr[u].chl[s[i]-'a']=++cnt;
        u=tr[u].chl[s[i]-'a'];
    }
    tr[u].b=true;
}
inline void get_nxt(){
    for(int i=0;i<26;++i)
        if(tr[0].chl[i])
            q.push(tr[0].chl[i]);
    while(!q.empty()){
        int u=q.front();q.pop();
        for(int i=0,j,c;i<26;++i){
            if(c=tr[u].chl[i]){
                q.push(c);j=tr[u].nxt;
                while(j&&!tr[j].chl[i])
                    j=tr[j].nxt;
                tr[c].nxt=tr[j].chl[i];
            }
        }
    }
}
//统计每个字符串在文章s中出现次数
inline void tot(char s[]){
    int l=strlen(s+1);
    for(int i=1,j=0;i<=l;++i){
        while(j&&!tr[j].chl[s[i]-'a'])
            j=tr[j].nxt;
        if(tr[j].chl[s[i]-'a'])
            j=tr[j].chl[s[i]-'a'];
        if(j) ++t[j];
    }
    for(int i=cnt;i;--i)
        if(tr[i].nxt) t[tr[i].nxt]+=t[i];
}

字典序

后缀数组

时间复杂度：\(O(nlogn)\)

#define N 200005
int a[N],sa[N],rk[N],ht[N],fir[N],sec[N],bu1[N],bu2[N],tmp[N],m;//第i小
inline void getSA(){
    memset(bu1,0,sizeof(bu1));
    for(int i=1;i<=m;++i) ++bu1[a[i]];
    for(int i=1;i<=m;++i) bu1[i]+=bu1[i-1];
    for(int i=m;i;--i) sa[bu1[a[i]]--]=i;
    rk[sa[1]]=1;
    for(int i=2;i<=m;++i){
        rk[sa[i]]=rk[sa[i-1]];
        if(a[sa[i]]!=a[sa[i-1]]) ++rk[sa[i]];
    }
    for(int t=1;rk[sa[m]]<m;t<<=1){
        memset(bu1,0,sizeof(bu1));
        memset(bu2,0,sizeof(bu2));
        for(int i=1;i<=m;++i){
            ++bu1[fir[i]=rk[i]];
            ++bu2[sec[i]=((i+t>m)?0:rk[i+t])]; 
        }
        for(int i=1;i<=m;++i) bu2[i]+=bu2[i-1];
        for(int i=m;i;--i) tmp[bu2[sec[i]]--]=i;
        for(int i=1;i<=m;++i) bu1[i]+=bu1[i-1];
        for(int i=m;i;--i) sa[bu1[fir[tmp[i]]]--]=tmp[i]; 
        rk[sa[1]]=1;
        for(int i=2;i<=m;++i){
            rk[sa[i]]=rk[sa[i-1]];
            if(fir[sa[i]]!=fir[sa[i-1]]||sec[sa[i]]!=sec[sa[i-1]]) ++rk[sa[i]];
        }
    }
    for(int i=1,j,k=0;i<=m;++i) {
        if(k) --k;
        j=sa[rk[i]-1];
        while(i+k<=n&&j+k<=n&&a[i+k]==a[j+k]) ++k;
        ht[rk[i]]=k;
    }
}

后缀自动机

时间复杂度：\(O()\)

回文串

manacher

时间复杂度：\(O(n)\)

#define N 200005
using namespace std;
int r[N],m,n,mx,id,ans;
char a[N];
inline int manacher(){
	for(int i=n;i;--i){
		a[i<<1]=a[i];
		a[i<<1|1]='#';
	}
	n=n<<1|1;mx=id=0;
	a[0]='$';a[1]=a[n+1]='#';
	for(int i=1;i<=n;++i){
		r[i]=i<mx?min(r[(id<<1)-i],mx-i):1;
		while(a[i+r[i]]==a[i-r[i]]) ++r[i];
		if(i+r[i]>mx) mx=i+r[i],id=i;
		ans=max(ans,r[i]-1);
	}
	return ans;
}

回文树

时间复杂度：\(O()\)

2017-01-26 19:18:10