字符串匹配
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