[关闭]
@LittleRewriter 2017-10-08T03:20:33.000000Z 字数 8136 阅读 934

字符串

字符串

事先声明，本Note并不是用来学习的。
因为后面的东西在下也没有听懂。
如果有什么建议的话欢迎指正吧。

hash

hash就是一个字符串到整数的映射，可以快速比较字符串是否相等
比较整数是O(1)的，可以快速比较
hash相等的两个字符串大概率相等，不等的话一定不等（准确判否）

RK-hash

将字符串看做base进制大整数。
例如，小写字母可以看做一个27进制的数字
每一位乘进制+当前这位，同时进行取模。
hash[i]=(hash[i-1]*base+s[i])%p
base可以随便取，31 131 13131是比较好的。
并且最好不要前导0。
p最好是longlong范围内的一个素数，如1e18+9 23333333333333333
也可以unsinged long long 自动溢出，不过有可能被卡掉。
也可以多取几个素数，提高正确率。
用map维护即可

取出s中[L,R]的hash

//以下所有运算都是在模大质数意义下进行。
首先取出hash[R]、hash[L-1]
然后在hash[L-1]对齐相减
hash[L,R]=hash[R]-hash[L-1]*pow(base,r-l+1)
由于幂只与区间长度有关，所以可以预处理。这样查询区间hash也是O(1)的。

hash合并

知道B的长度L，在A后面补位
hash[A+B]=hash[A]*pow(base,L)%p+hash[B]

求最长公共前缀(LCP)

二分查找前缀的hash值，log复杂度

判断字典序大小

求出LCP比较后一位即可

哈希表

用一个链表，O(1)查询

  1. vector<ULL> v[1005];
  2. v[h%q].push_back(h);

X-Or版本 RK-hash

hash[i]=(hash[i-1]*base^s[i])%p
无法利用前缀和性质，但可以避免被卡

POJ2758

给定一个字符串, 要求维护两种操作:在字符串中插入一个字符,询问某两个位置开始的最长公共前缀。插入操作<=200, 字符串长度<=5w, 查询操作<=2w。

插入字符直接重构即可
查询是裸LCP
下面的可以当做LCP模板

  1. #include<cstdio>
  2. #include<algorithm>
  3. #include<cstring>
  4. using namespace std;
  5. int L,cc;
  6. char s[55005];
  7. char tmps[10];
  8. int c[55005];
  9. unsigned long long hash[55005];
  10. unsigned long long pow[55005];
  11. int main(){
  12. //  freopen("data.in","r",stdin);
  13.     pow[0]=1;
  14.     for(int i=1;i<55005;i++) pow[i]=pow[i-1]*131;
  15.     scanf("%s",s+1);
  16.     cc=L=strlen(s+1);//s 1..L 
  17.     for(int i=1;i<=L;i++) {
  18.         c[i]=c[i-1]+1;
  19.     }
  20.     for(int i=1;i<=L;i++){
  21.         hash[i]=hash[i-1]*131+s[i]-'a'+1;
  22.     }
  23. //  add(2,1);
  24. //  printf("%d %d\n",getpos(1),getpos(3));
  25.     int n;
  26.     scanf("%d",&n);
  27.     while(n--){
  28.         scanf("%s",tmps);
  29.     /// putchar('#');
  30.     //      for(int i=1;i<=cc;i++){
  31.     //          
  32.     //          printf(" %d",c[i]);
  33.     //          
  34.     //      }
  35.     //      puts("");
  36.         if(tmps[0]=='I'){
  37.             scanf("%s",tmps);
  38.             int pos;
  39.             scanf("%d",&pos);
  40.             if(pos>L){
  41.                 s[L+1]=tmps[0];
  42.                 hash[L+1]=hash[L]*131+s[L+1]-'a'+1;
  43.             }else{
  44.                 for(int i=L;i>=pos;i--) s[i+1]=s[i];
  45.                 s[pos]=tmps[0];
  46.                 for(int i=pos;i<=L+1;i++) hash[i]=hash[i-1]*131+s[i]-'a'+1;
  47.                 int initpos=lower_bound(c+1,c+1+cc,pos)-c;
  48.                 for(int i=initpos;i<=cc;i++){
  49.                     c[i]++;
  50.                 }
  51.             }
  52.             L++;
  53.         }else{
  54.             int x,y;
  55.             scanf("%d%d",&x,&y);
  56.             x=c[x];y=c[y];
  57.             int l=0,r=min(L-x,L-y)+2,mid;
  58.             while(r-l>1){
  59.                 mid=(l+r)/2;
  60.                 if(hash[x+mid-1]-hash[x-1]*pow[mid]==hash[y+mid-1]-hash[y-1]*pow[mid]) l=mid;
  61.                 else r=mid;
  62.             }
  63.             printf("%d\n",l);
  64.         }
  65.     }
  68.     return 0;
  69. }

BZOJ3555

N个长度为L的字符串，问有多少对只有一位不同。

对N个字符串求整串hash
然后不考虑某一类看有多少相同也就是删去某一位
用一个map来存储

  1. #include<cstdio>
  2. #include<cstring>
  3. #include<algorithm>
  4. #include<map>
  5. using namespace std;
  6. int n,m,k;
  7. long long ans;
  8. typedef unsigned long long llu;
  9. char s[30005][205];
  10. llu hash[30005];
  11. map<llu,int> mp;
  12. llu pow[205];
  13. int main(){
  14.     scanf("%d%d%d",&n,&m,&k);
  15.     pow[0]=1;
  16.     for(int i=1;i<=m;i++) pow[i]=pow[i-1]*13131;
  17.     for(int i=0;i<n;i++){
  18.         scanf("%s",s[i]);
  19.     }
  20.     for(int i=0;i<n;i++){
  21.         for(int j=0;j<m;j++){
  22.             hash[i]=hash[i]*13131+s[i][j];
  23.         }
  24.     }
  25.     for(int p=0;p<m;p++){
  26.         mp.clear();
  27.         for(int i=0;i<n;i++){
  28.             llu h=hash[i]-s[i][p]*pow[m-p-1];
  29.             mp[h]++;
  30.         }
  31.         for(map< llu ,int>::iterator it=mp.begin();it!=mp.end();it++){
  32.             if(it->second){
  33.                 ans+=it->second*(it->second-1)/2;
  34.             }
  35.         }
  36.     }
  38.     printf("%lld\n",ans);
  39.     return 0;
  40. }

KMP

朴素匹配算法

一位一位的匹配
O(nm)

KMP匹配

//这个东西的原理由于在下水平有限真的说不清..所以实在不行的话就背代码吧
//hzk神犇讲的要好多了..ORZ!
用nxt数组表示最长的后缀=前缀位置
例如
序：12345678
字：abcababc
值：00012123
预处理nxt时，假设nxt[L]是处理完毕的。处理nxt[L+1]时，首先试图加一个元素上去，看能不能行，否则我们就不断的取nxt直到符合条件。
假设模式串[L,k]与主串[i,j]是可以匹配的，并且在j处不相等。现在模式串向后错一位，而我们现在要匹配[L+1]，对应的是[i+1]，由上可知[L+1,k]与[i+1,j]可匹配，因此我们通过nxt这个数组变换一下，就可以将匹配的后缀转化为前缀，跳过一部分继续匹配。
模板：

  1. 串为s,t
  2. int j=0;
  3.    for(int i=2;i<=m;i++){
  4.      while(j&&s[i]!=s[j+1]) j=nxt[j];
  5.      if(s[i]==s[j+1]) j++;
  6.     nxt[i]=j;
  7.  }
  9. char t[]; n
  11. int j =0;
  12. for(int i=1;i<=n;i++){
  13.     while(j && t[i]!=s[j+1]) j=nxt[j];
  14.     if(t[i] == s[j+1]) j++;
  15.     if(j==m){
  16.         //...
  17.         j=nxt[j];
  18.     }
  19. }

由于后缀=前缀没有二分性质，只能递推求得。
所以不能hash。

最小循环节

长度为len-next[len]
如果l整除len-next[len]那么说明这个串可以完整被分成循环节。
否则就有l%(len-next[len])是除去循环节的部分。

POJ2752

求所有x使得串的长度为x的前缀和x的后缀相等。

不停取nxt即可。

  1. #include<cstdio>
  2. #include<algorithm>
  3. #include<cstring>
  4. //by zrt
  5. //problem:
  6. using namespace std;
  7. char s[400005];
  8. int nxt[400005];
  9. int num[400005];
  10. int tot;
  11. int main(){
  12.     #ifdef LOCAL
  13.     freopen("in.txt","r",stdin);
  14.     freopen("out.txt","w",stdout);
  15.     #endif
  16.     while(~scanf("%s",s)){
  17.         int j=-1;
  18.         nxt[0]=j;
  19.         int l=strlen(s);
  20.         for(int i=1;i<l;i++){
  21.             while((~j)&&s[j+1]!=s[i]) j=nxt[j];
  22.             if(s[i]==s[j+1]) j++;
  23.             nxt[i]=j;
  24.         }
  25.         tot=0;
  26.         for(int i=l-1;~i;i=nxt[i])
  27.             num[++tot]=i+1;
  28.         for(int i=tot;i;i--){
  29.             printf("%d ",num[i]);
  30.         }
  31.         putchar('\n');
  32.     }
  33.     return 0;
  34. }

BZOJ3670

求num数组一一对于字符串S的前i个字符构成的子串，既是它的后缀同时又是它的前缀，并且该后缀与该前缀不重叠,将这种字符串的数量记作num[i]。

卡着不重叠的界来递推，一旦超范围就强制搞回去。

  1. #include<cstdio>
  2. #include<cstring>
  3. #include<algorithm>
  4. using namespace std;
  5. int n;
  6. int l;
  7. const int MAXN=1000005;
  8. char s[MAXN];
  9. int nxt[MAXN];
  10. int num[MAXN];
  11. int sum[MAXN];
  12. const int mod=1e9+7;
  13. void solve(){
  14.     nxt[1]=0;
  15.     int L=strlen(s+1);
  16.     int j=0;
  17.     for(int i=2;i<=L;i++){
  18.         while(j&&s[j+1]!=s[i]) j=nxt[j];
  19.         if(s[j+1]==s[i]) j++;
  20.         nxt[i]=j;
  21.     }
  22.     memset(sum,0,sizeof sum);
  23.     memset(num,0,sizeof num);
  24.     sum[0]=1;
  25.     for(int i=1;i<=L;i++) sum[i]=sum[nxt[i]]+1;
  26.     j=0;
  27.     for(int i=2;i<=L;i++){
  28.         while(j&&s[j+1]!=s[i]) j=nxt[j];
  29.         if(s[j+1]==s[i]) j++;
  30.         while(j>i/2) j=nxt[j];//防止超过i/2导致重叠
  31.         num[i]=sum[j]-1;
  32.     }
  33. //  for(int i=1;i<=L;i++) printf("%d ",num[i]);
  34. //      puts("");
  35.     long long ans=1;
  36.     for(int i=1;i<=L;i++) ans=ans*(num[i]+1)%mod;
  37.     printf("%lld\n",ans);
  38. }
  39. int main(){
  40.     scanf("%d",&n);
  41.     for(int i=0;i<n;i++){
  42.         scanf("%s",s+1);
  43.         solve();
  44.     }
  45.     return 0;
  46. }

D6T3

见题解

Manachar

hash:O(nlogn)
abba aba
偶数中心在空隙，奇数中心为某一字符
可以加一个符号将偶数变成奇数，如
#a#b#b#a#，回文串半径成为两倍
预处理一个数组表示能扩展的半径
abcbaabcba
1131111311

  1. //暴力
  2. for(int i=1;i<=L;++i){
  3.     r[i]=1;
  4.     while(s[i-r[i]]==s[i+r[i]]) r[i]++
  5. }
  6. 在边上加一个边界可以判断结束，最坏O(n^2)

如果我们要拓展i，我们找到i关于id的对称点(2id-i)，该点的回文半径是已知的。
例如，
abacabac
12345678
求6处的b时，id=3，所以对称为2处的b。因此r[i]初值为r[2id-i]，但观察发现其实还是能扩展的，所以还需要继续暴力。

  1. int mx=max{i+r[i]-1}//能够达到最靠右的元素
  2. int id;//mx取到最大值时取到的i
  3. for(int i=1;i<=L;++i){
  4.     r[i]=min(r[2id-i],mx-i);//有可能超过半径
  5.     while(s[i-r[i]]==s[i+r[i]]) r[i]++;
  6.     if(i+r[i]-1>mx) mx=i+r[i]-1,id=i;
  7. }
  8. 复杂度O(n).

BZOJ2342

第一段正hash=第二段反hash=第三段正hash=第四段反hash
也可以在manachar r[i]++处加一个check函数判断是否是双回文

BZOJ3676

由于回文串删掉两边仍是回文串，所以其实可以建一棵树。
查询字符串出现次数，然后可以打一个+1标记
打完以后再从叶到根push一遍，得到了所有回文串对应的出现次数
以hash来建树。

exKMP

a串的后缀与b串LCP
先求b串后缀与自己的LCP

  1. //暴力
  2. for(int i=1;i<=n;++i){
  3.     p[i]=0;
  4.     while(b[i+p[i]]==b[p[i]+1]) ++p[i];
  5. }

。。。没听懂，我腿裙吧.jpg

  1. for(int i=1;i<=n;++i){
  2.     p[i]=min(mx-i,p[i-id]);
  3.     while(b[i+p[i]]==b[p[i]+1]) ++p[i];
  4.     if(i+p[i]>mx){
  5.         id=i;
  6.         mx=i+p[i];
  7.     }
  8. }

tyvj1068

给你两个串A，B，可以得到从A的任意位开始的子串和B匹配的长度。
给定K个询问，对于每个询问给定一个x，求出匹配长度恰为x的位置有多少个。

模板题

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int n,m,k;
  4. char sa[210005],sb[210005];
  5. int p[200005],q[200005];
  6. int ans[200005];
  7. int main(){
  8.     scanf("%d%d%d%s%s",&n,&m,&k,sa,sb);
  9.     //calc sb
  10.     int mx=0,id=0;
  11.     p[0]=m;
  12.     for(int i=1;i<m;i++){
  13.         if(i<=mx){
  14.             p[i]=min(mx-i,p[i-id]);
  15.         }
  16.         while(sb[i+p[i]]&&sb[i+p[i]]==sb[p[i]]) p[i]++;
  17.         if(i+p[i]>mx){
  18.             mx=i+p[i];
  19.             id=i;
  20.         }
  21.     }
  23.     mx=0,id=0;
  24.     for(int i=0;i<n;i++){
  25.         if(i<=mx){
  26.             q[i]=min(mx-i,p[i-id]);
  27.         }
  28.         while(sa[i+q[i]]&&sb[q[i]]&&sa[i+q[i]]==sb[q[i]]) q[i]++;
  29.         if(i+q[i]>mx){
  30.             mx=i+q[i];
  31.             id=i;
  32.         }
  33.     }
  34.     for(int i=0;i<n;i++) ans[q[i]]++;
  35.     for(int i=0,x;i<k;i++){
  36.         scanf("%d",&x);
  37.         printf("%d\n",ans[x]);
  38.     }
  39.     return 0;
  40. }

Trie树

每个节点代表一个串

  1. int trie[100000][26];
  2. int tot;
  3. void insert(char* s){
  4.     int p=0;
  5.     for(int i=0;s[i];++i){
  6.         if(trie[p][s[i]-'a') id=trie[p][s[i]-'a'];
  7.         else id=trie[p][s[i]-'a']=++tot;
  8.     }
  9.     flag[p]++;//记录以p结尾的有几个
  10. }

比较

直接插入，DFS，遇见flag>0的就输出来

LCP

两个点的LCA的深度是LCP

POJ3764

已知数组a，求max{a[i]^a[j]}

对每个a[i]，找一个抑或最大的a[j]
由于1^1=0,1^0=1,0^0=0
将每个数变成二进制串，将所有的串建成Trie树，从根开始走，然后贪心，优先为1。

AC自动机

把Trie树上不存在的孩子用它fail节点的孩子补出来。
fail节点的概念与KMP的next类似，可以用一次bfs来求出。
若trie[i][x]存在，则fail[trie[i][x]]=trie[fail[i]][x]。
否则，trie[i][x]=trie[fail[i]][x]。
这啥玩意啊.jpg

hdu2222

多模式串匹配模板题。

  1. #include<cstdio>
  2. #include<cstring>
  3. #include<algorithm>
  4. #include<queue>
  5. //by zrt
  6. //problem:
  7. using namespace std;
  8. int tt;
  9. int n; 
  10. int pos;
  11. int nxt[500005][26];
  12. int fail[500005];
  13. int flag[500005],ok[500005];
  14. int newnode(){
  15.     memset(nxt[pos],0,sizeof nxt[pos]);
  16.     fail[pos]=flag[pos]=ok[pos]=0;
  17.     return pos++;
  18. }
  19. char s[1000005];
  20. void insert(char*s){
  21.     int p=0;
  22.     for(int i=0;s[i];i++){
  23.         p=nxt[p][s[i]-'a']?nxt[p][s[i]-'a']:nxt[p][s[i]-'a']=newnode();
  24.     }
  25.     flag[p]++;
  26. }
  27. queue<int> q;
  28. void makefail(){
  29.     q.push(0);
  30.     while(!q.empty()){
  31.         int x=q.front();q.pop();
  32.         for(int i=0;i<26;i++){
  33.             if(nxt[x][i]){
  34.                 q.push(nxt[x][i]);
  35.                 if(x)fail[nxt[x][i]]=nxt[fail[x]][i];
  36.             }else nxt[x][i]=nxt[fail[x]][i];
  37.         }
  38.     }
  39. }
  40. bool vis[500005];
  41. int find(char*s){
  42.     memset(vis,0,sizeof vis);
  43.     int p=0;
  44.     int ans=0;
  45.     for(int i=0;s[i];i++){
  46.         p=nxt[p][s[i]-'a'];
  47.         for(int j=p;j;j=fail[j]){
  48.             if(vis[j]) break;
  49.             vis[j]=1;
  50.             if(flag[j]) ok[j]=1;
  51.         }
  52.     }
  53.     for(int i=1;i<pos;i++) if(ok[i]) ans+=flag[i];
  54.     return ans;
  55. }
  56. int main(){
  57.     #ifdef LOCAL
  58.     freopen("in.txt","r",stdin);
  59.     freopen("out.txt","w",stdout);
  60.     #endif
  61.     scanf("%d",&tt);
  62.     while(tt--){
  63.         pos=1;
  64.         memset(nxt[0],0,sizeof nxt[0]);
  65.         scanf("%d",&n);
  66.         for(int i=0;i<n;i++){
  67.             scanf("%s",s);
  68.             insert(s);
  69.         }
  70.         makefail();
  71.         scanf("%s",s);
  72.         printf("%d\n",find(s));
  73.     }
  74.     return 0;
  75. }

bzoj2938/hzwer5049

二进制病毒审查委员会最近发现了如下的规律：某些确定的二进制串是病毒的代码。如果某段代码中不存在任何一段病毒代码，那么我们就称这段代码是安全的。现在委员会已经找出了所有的病毒代码段，试问，是否存在一个无限长的安全的二进制代码。
示例：
例如如果{011, 11, 00000}为病毒代码段，那么一个可能的无限长安全代码就是010101…。如果{01, 11, 000000}为病毒代码段，那么就不存在一个无限长的安全代码。
任务：
请写一个程序：
读入病毒代码；
判断是否存在一个无限长的安全代码；
将结果输出

如果Trie图中存在环就能生成无限长代码。否则就挂了。
找环拓扑即可。

添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注