给两个长度不超过50000的串，A串可每次截连续一段复制出来，求最少复制几次能得到B串。
方法一：SAM。不会。
嗯好会了。
1 #include<stdio.h> 2 #include<string.h> 3 #include<algorithm> 4 #include<stdlib.h> 5 //#include<iostream> 6 //#include<time.h> 7 using namespace std; 8 9 int n,m; 10 #define maxn 200011*2 11 char s[maxn],p[maxn]; 12 struct SAM 13 { 14 int ch[maxn][26],size,last,pre[maxn],pos[maxn]; 15 SAM() 16 { 17 size=0; 18 memset(ch[0],0,sizeof(ch[0])); 19 pre[0]=-1; 20 } 21 int idx(char c) {return c-'A';} 22 void insert(char c,int p) 23 { 24 int id=idx(c),x=++size; 25 memset(ch[x],0,sizeof(ch[x])); pos[x]=p; 26 int y=last; 27 for (;y!=-1 && !ch[y][id];y=pre[y]) ch[y][id]=x; 28 last=x; 29 if (y==-1) pre[x]=0; 30 else 31 { 32 if (pos[ch[y][id]]==pos[y]+1) pre[x]=ch[y][id]; 33 else 34 { 35 int z=ch[y][id],w=++size; 36 memcpy(ch[w],ch[z],sizeof(ch[z])); 37 pos[w]=pos[y]+1; pre[w]=pre[z]; 38 pre[z]=pre[x]=w; 39 for (;y!=-1 && ch[y][id]==z;y=pre[y]) ch[y][id]=w; 40 } 41 } 42 } 43 }sam; 44 45 int main() 46 { 47 scanf("%d%d",&n,&m); 48 for (int i=1;i<=n;i++) 49 { 50 char c;while (!((c=getchar())>='A' && c<='Z')); 51 sam.insert(c,i); 52 } 53 for (int i=1;i<=m;i++) while (!((p[i]=getchar())>='A' && p[i]<='Z')); 54 int pos=1,ans=0; 55 while (pos<=m) 56 { 57 int now=0; 58 while (pos<=m && sam.ch[now][p[pos]-'A']) now=sam.ch[now][p[pos]-'A'],pos++; 59 // cout<<endl; 60 ans++; 61 } 62 printf("%d ",ans); 63 return 0; 64 }
方法二：其实就是拿B去A上面匹配若干次。多次匹配的话可以把A先建个后缀数组，然后每次二分到B的位置搞匹配。匹配一次怕太慢的话，用hash吧！二分匹配长度找到第一个不可匹配的位置，就可以算匹配长度啦！
1 #include<stdio.h> 2 #include<string.h> 3 #include<stdlib.h> 4 #include<algorithm> 5 //#include<iostream> 6 using namespace std; 7 8 int n,m; 9 #define maxn 50011 10 char t[maxn],p[maxn],c; 11 int ht[maxn],hp[maxn]; 12 int sa[maxn],cnt[maxn],rank[maxn],y[maxn]; 13 void makesa(char* s) 14 { 15 int n=strlen(s),m=26; 16 for (int i=0;i<m;i++) cnt[i]=0; 17 for (int i=0;i<n;i++) cnt[rank[i]=s[i]-'A']++; 18 for (int i=1;i<m;i++) cnt[i]+=cnt[i-1]; 19 for (int i=n-1;i>=0;i--) sa[--cnt[rank[i]]]=i; 20 for (int k=1;k<=n;k<<=1) 21 { 22 int p=0; 23 for (int i=n-k;i<n;i++) y[p++]=i; 24 for (int i=0;i<n;i++) if (sa[i]>=k) y[p++]=sa[i]-k; 25 for (int i=0;i<m;i++) cnt[i]=0; 26 for (int i=0;i<n;i++) cnt[rank[y[i]]]++; 27 for (int i=1;i<m;i++) cnt[i]+=cnt[i-1]; 28 for (int i=n-1;i>=0;i--) sa[--cnt[rank[y[i]]]]=y[i]; 29 memcpy(y,rank,sizeof(y)); 30 p=0;rank[sa[0]]=0; 31 for (int i=1;i<n;i++) 32 rank[sa[i]]=y[sa[i]]==y[sa[i-1]] && ((sa[i]+k>=n && sa[i-1]+k>=n) 33 || (sa[i]+k<n && sa[i-1]+k<n && y[sa[i]+k]==y[sa[i-1]+k]))?p:++p; 34 if (p==n-1) break; 35 m=p+1; 36 } 37 } 38 void makeh(char* s,int* h) 39 { 40 int n=strlen(s); 41 h[0]=s[0]-'A'; 42 for (int i=1;i<n;i++) 43 h[i]=h[i-1]*27+s[i]-'A'; 44 } 45 int pw[maxn]; 46 void makepw(int n) 47 { 48 pw[0]=1; 49 for (int i=1;i<=n;i++) 50 pw[i]=pw[i-1]*27; 51 } 52 bool ok(int x,int y) 53 { 54 int L=0,R=min(n-x,m-y); 55 while (L<R) 56 { 57 if (ht[x+mid-1]-ht[x-1]*pw[mid]==hp[y+mid-1]-hp[y-1]*pw[mid]) L=mid; 58 else R=mid-1; 59 } 60 return p[y+L]<=t[x+L]; 61 } 62 int lcp(int x,int y) 63 { 64 int now=0; 65 while (x<n && y<m && t[x]==p[y]) now++,x++,y++; 66 return now; 67 } 68 void play(int &x) 69 { 70 int L=0,R=n; 71 while (L<R) 72 { 73 int mid=(L+R)>>1; 74 if (ok(sa[mid],x)) R=mid; 75 else L=mid+1; 76 } 77 if (!L) x+=lcp(sa[L],x); 78 else if (L<n) x+=max(lcp(sa[L-1],x),lcp(sa[L],x)); 79 else x+=lcp(sa[n-1],x); 80 } 81 bool isalpha(char c) {return c>='A' && c<='Z';} 82 int main() 83 { 84 scanf("%d%d",&n,&m); 85 t[n]=' ';p[m]=' '; 86 for (int i=0;i<n;i++) 87 { 88 while (!isalpha(c=getchar())); 89 t[i]=c; 90 } 91 for (int i=0;i<m;i++) 92 { 93 while (!isalpha(c=getchar())); 94 p[i]=c; 95 } 96 makesa(t); 97 makeh(t,ht);makeh(p,hp);makepw(max(n,m)); 98 int now=0,ans=0; 99 while (now<m) play(now),ans++; 100 printf("%d ",ans); 101 return 0; 102 }