ACM字符串题目及源代码.doc

31zhxfl 目录Hdu1403最长公共子串2Pku1743不可以重复的最长重复子串4Pku3261可以重叠k次的最长重复子串7Spoj694不相同的子串的个数10Hdu3068最长回文（扩展kmp）13Timus 1297 最长回文子串后缀数组解法16Pku3693 重复次数最多的连续重复子串20nlogn后缀数组TLE22Kmp24SPOJ687重复次数最多的连续重复子串25Pku3693同上题一样原理29Pku3415 长度不小于k的公共子串的个数29 Hdu1403最长公共子串Sample InputbananacianaicSample Output3#include#include#includeusing namespace std;#define maxn 200005int wamaxn,wbmaxn,wvmaxn,whmaxn;int cmp(int *r,int a,int b,int l)return ra=rb&ra+l=rb+l;void da(char *r,int *sa,int n,int m) int i,j,p,*x=wa,*y=wb,*t; for(i=0;im;i+) whi=0; for(i=0;in;i+) whxi=ri+; for(i=1;i=0;i-) sa-whxi=i; for(j=1,p=1;pn)break; for(p=0,i=n-j;in;i+) yp+=i; for(i=0;i=j) yp+=sai-j; for(i=0;in;i+) wvi=xyi; for(i=0;im;i+) whi=0; for(i=0;in;i+) whwvi+; for(i=1;i=0;i-) sa-whwvi=yi; for(t=x,x=y,y=t,p=1,xsa0=0,i=1;in;i+) xsai=cmp(y,sai-1,sai,j)?p-1:p+; return;int rankmaxn,heightmaxn;void calheight(char *r,int *sa,int n) int i,j,k=0; for(i=1;in;i+) ranksai=i; for(i=0;in;heightranki+=k) for(k?k-:0,j=saranki-1;ri+k=rj+k;k+); return ;int judge(int i,int n,int *sa) int t1,t2; if(sai=n)t1=1; else t1=0; if(sai-1=n)t2=1; else t2=0; if(t1!=t2)return 1; else return 0;char rmaxn;char tmpmaxn;int samaxn;int main() int i,j,n,m; /freopen(a.txt,r,stdin); while(scanf(%s%s,&r,&tmp)!=EOF) n=strlen(r); m=strlen(tmp); rn= ; for(i=0,j=n+1;im;i+,j+)rj=tmpi; n=n+m+1; /for(i=0;in;i+)printf(%c,ri);printf(n); da(r,sa,n,); calheight(r,sa,n); int max=0; /for(i=0;in;i+)printf(%d,sai);printf(n); for(i=1;imax&judge(i,n-m-1,sa)max=heighti; printf(%dn,max); return 0;Pku1743不可以重复的最长重复子串Time Limit: 1000MSMemory Limit: 30000KDescriptionA musical melody is represented as a sequence of N (1=N=20000)notes that are integers in the range 1.88, each representing a key on the piano. It is unfortunate but true that this representation of melodies ignores the notion of musical timing; but, this programming task is about notes and not timings. Many composers structure their music around a repeating &qout;theme&qout;, which, being a subsequence of an entire melody, is a sequence of integers in our representation. A subsequence of a melody is a theme if it: is at least five notes long appears (potentially transposed - see below) again somewhere else in the piece of music is disjoint from (i.e., non-overlapping with) at least one of its other appearance(s) Transposed means that a constant positive or negative value is added to every note value in the theme subsequence. Given a melody, compute the length (number of notes) of the longest theme. One second time limit for this problems solutions! InputThe input contains several test cases. The first line of each test case contains the integer N. The following n integers represent the sequence of notes. The last test case is followed by one zero. OutputFor each test case, the output file should contain a single line with a single integer that represents the length of the longest theme. If there are no themes, output 0. Sample Input3025 27 30 34 39 45 52 60 69 79 69 60 52 45 39 34 30 26 22 1882 78 74 70 66 67 64 60 65 800Sample Output5#include#include#includeusing namespace std;#define maxn 20010int wamaxn,wbmaxn,wvmaxn,whmaxn;int cmp(int *r,int a,int b,int l)return ra=rb&ra+l=rb+l;void da(int *r,int *sa,int n,int m) int i,j,p,*x=wa,*y=wb,*t; for(i=0;im;i+) whi=0; for(i=0;in;i+) whxi=ri+; for(i=1;i=0;i-) sa-whxi=i; for(j=1,p=1;pn)break; for(p=0,i=n-j;in;i+) yp+=i; for(i=0;i=j) yp+=sai-j; for(i=0;in;i+) wvi=xyi; for(i=0;im;i+) whi=0; for(i=0;in;i+) whwvi+; for(i=1;i=0;i-) sa-whwvi=yi; for(t=x,x=y,y=t,p=1,xsa0=0,i=1;in;i+) xsai=cmp(y,sai-1,sai,j)?p-1:p+; return;int rankmaxn,heightmaxn;void calheight(int *r,int *sa,int n) int i,j,k=0; for(i=1;in;i+) ranksai=i; for(i=0;in;heightranki+=k) for(k?k-:0,j=saranki-1;ri+k=rj+k;k+); return ;int rmaxn;int samaxn;bool Get(int k,int n) int i,mmin=sa0,mmax=sa0; for(i=1;in;i+) if(heighti=k) return 1; return 0;int xmaxn;int main() int i,n; /freopen(a.txt,r,stdin); while(scanf(%d,&n)&n) for(i=0;in;i+)scanf(%d,&xi); if(n=1) printf(0n); continue; for(i=0;in-1;i+)ri=xi+1-xi+88; n-; da(r,sa,n,88+88); calheight(r,sa,n); int left=0,right=n/2; int ans=0; while(left=0&Get(mid,n) ans=mid; left=mid+1; else right=mid-1; if(ans+15)printf(0n); else printf(%dn,ans+1); return 0;Pku3261可以重叠k次的最长重复子串Time Limit: 5000MSMemory Limit: 65536KTotal Submissions: 4486Accepted: 1904Case Time Limit: 2000MSDescriptionFarmer John has noticed that the quality of milk given by his cows varies from day to day. On further investigation, he discovered that although he cant predict the quality of milk from one day to the next, there are some regular patterns in the daily milk quality.To perform a rigorous study, he has invented a complex classification scheme by which each milk sample is recorded as an integer between 0 and 1,000,000 inclusive, and has recorded data from a single cow over N (1 N 20,000) days. He wishes to find the longest pattern of samples which repeats identically at least K (2 K N) times. This may include overlapping patterns - 1 2 3 2 3 2 3 1 repeats 2 3 2 3 twice, for example.Help Farmer John by finding the longest repeating subsequence in the sequence of samples. It is guaranteed that at least one subsequence is repeated at least K times.InputLine 1: Two space-separated integers: N and K Lines 2.N+1: N integers, one per line, the quality of the milk on day i appears on the ith line.OutputLine 1: One integer, the length of the longest pattern which occurs at least K timesSample Input8 212323231Sample Output4#include#include#includeusing namespace std;#define maxn 1000010int wamaxn,wbmaxn,wvmaxn,whmaxn;int cmp(int *r,int a,int b,int l)return ra=rb&ra+l=rb+l;void da(int *r,int *sa,int n,int m) int i,j,p,*x=wa,*y=wb,*t; for(i=0;im;i+) whi=0; for(i=0;in;i+) whxi=ri+; for(i=1;i=0;i-) sa-whxi=i; for(j=1,p=1;p=n)break; for(p=0,i=n-j;in;i+) yp+=i; for(i=0;i=j) yp+=sai-j; for(i=0;in;i+) wvi=xyi; for(i=0;im;i+) whi=0; for(i=0;in;i+) whwvi+; for(i=1;i=0;i-) sa-whwvi=yi; for(t=x,x=y,y=t,p=1,xsa0=0,i=1;in;i+) xsai=cmp(y,sai-1,sai,j)?p-1:p+; return;int rmaxn;int samaxn;int rankmaxn,heightmaxn;void calheight(int *r,int *sa,int n) int i,j,k=0; for(i=0;in;i+) ranksai=i; for(i=0;i=0) for(k?k-:0,j=saranki-1;ri+k=rj+k&i+kn&j+kn;k+); return ;bool Get(int k,int n,int t) int i,num=1; for(i=1;in;i+) if(heighti=t)return 1; return 0;int xmaxn;void ceshi(int n) int i; for(i=0;in;i+)printf(%d ,sai);printf(n); for(i=0;in;i+)printf(%d ,ranki);printf(n); for(i=0;in;i+)printf(%d ,heighti);printf(n);int main() int i,n,k; /freopen(a.txt,r,stdin); while(scanf(%d%d,&n,&k)!=EOF) for(i=0;in;i+)scanf(%d,&ri); da(r,sa,n,1000001); calheight(r,sa,n); /ceshi(n); int left=0,right=n; int ans=0; while(left=0&Get(mid,n,k) ans=mid; left=mid+1; else right=mid-1; printf(%dn,ans); return 0;Spoj694不相同的子串的个数 Given a string, we need to find the total number of its distinct substrings.InputT- number of test cases. T=20;Each test case consists of one string, whose length is = 1000OutputFor each test case output one number saying the number of distinct substrings.ExampleSample Input:2CCCCCABABASample Output:59Explanation for the testcase with string ABABA: len=1 : A,Blen=2 : AB,BAlen=3 : ABA,BABlen=4 : ABAB,BABAlen=5 : ABABAThus, total number of distinct substrings is 9.#include#include#includeusing namespace std;#define maxn 1000010int wamaxn,wbmaxn,wvmaxn,whmaxn;int cmp(int *r,int a,int b,int j,int n) int x=ra+j; int y=rb+j; if(a+j=n)x=-1; if(b+j=n)y=-1; return ra=rb&x=y;void da(int *r,int *sa,int n,int m) int i,j,p,*x=wa,*y=wb,*t; for(i=0;im;i+) whi=0; for(i=0;in;i+) whxi=ri+; for(i=1;i=0;i-) sa-whxi=i; for(j=1,p=1;pn;j*=2,m=p) / printf(X:);/ for(i=0;i=n)break; for(p=0,i=n-j;in;i+) yp+=i; for(i=0;i=j) yp+=sai-j;/ printf(Y:);/ for(i=0;in;i+)printf(%d ,yi);printf(n); for(i=0;in;i+) wvi=xyi; for(i=0;im;i+) whi=0; for(i=0;in;i+) whwvi+; for(i=1;i=0;i-) sa-whwvi=yi;/ printf(sa:);/ for(i=0;in;i+)printf(%d ,sai);printf(nn); for(t=x,x=y,y=t,p=1,xsa0=0,i=1;in;i+) xsai=cmp(y,sai-1,sai,j,n)?p-1:p+; / printf(X:);/ for(i=0;in;i+)printf(%d ,xi);printf(n); return;int rmaxn,samaxn,rankmaxn,heightmaxn;void calheight(int *r,int *sa,int n) int i,j,k=0; for(i=0;in;i+) ranksai=i; for(i=0;i=0) for(k?k-:0,j=saranki-1;ri+k=rj+k&i+kn&j+kn;k+); return ;int Get(int n,int *sa) int i,ans=n-sa0; for(i=1;in;i+) ans+=n-sai-heighti; return ans;void ceshi(int n) int i; /for(i=0;in;i+)printf(%d ,ri);printf(n); for(i=0;in;i+)printf(%d ,sai);printf(n); / for(i=0;in;i+)printf(%d ,ranki);printf(n); for(i=1;in;i+)printf(%d ,heighti);printf(n);char smaxn;int main() int i,n,k,T; scanf(%d,&T); while(T-) scanf(%s,&s); n=strlen(s); for(i=0;in;i+)ri=si-A+1; da(r,sa,n,130); calheight(r,sa,n); / ceshi(n); printf(%dn,Get(n,sa); return 0;Hdu3068最长回文（扩展kmp）Time Limit: 4000/2000 MS (Java/Others)Memory Limit: 32768/32768 K (Java/Others)Problem Description给出一个只由小写英文字符a,b,c.y,z组成的字符串S,求S中最长回文串的长度.回文就是正反读都是一样的字符串,如aba, abba等Input输入有多组case,不超过120组,每组输入为一行小写英文字符a,b,c.y,z组成的字符串S两组case之间由空行隔开(该空行不用处理)字符串长度len = 110000Output每一行一个整数x,对应一组case,表示该组case的字符串中所包含的最长回文长度.Sample InputaaaaababSample Output43/扩展kmp#include using namespace std;#define Max 110005#define inf 10000000char aMax;/主串char bMax;/模式串int nextbMax,nexta1Max,nexta2Max,ans;void kmp1(char *b,int *nextb) int i,j,k,t; i=0; while(bi=bi+1)i+; nextb1=i; k=1; for(i=2;bi;i+) if(nextbi-k+inextbk+k)nextbi=nextbi-k; else j=nextbk+k-i; if(j0)j=0; while(bj=bj+i&bi+j)j+; nextbi=j; k=i; void kmp2(char *a,char *b,int *nexta,int *nextb,int len) kmp1(b,nextb); int i,j,k; i=0; while(ai=bi)i+; nexta0=i; k=0; for(i=1;ilen;i+) if(nextbi-k+inextak+k)nextai=nextbi-k; else j=nextak+k-i; if(j0)j=0; while(bj=aj+i&bj&j+ilen)j+; nextai=j; k=i; void rev(char *a,int len) char t; for(int i=0;ilen/2;i+)t=ai,ai=alen-1-i,alen-1-i=t;void solve(char *a,int len) if(len=ans|len1; int i; for(i=mid;ilen;i+) bi-mid=ai; bi-mid=0; rev(a,len); kmp2(a,b,nexta1,nextb,len); rev(a,len); for(i=0;imid;i+) bi=amid-i-1; bi=0; kmp2(a,b,nexta2,nextb,len); nexta1len=nexta2len=0; for(i=0;i=(mid-i)/2) int x=mid-i+2*nexta1len-i; if(xans)ans=x; for(i=mid;i=(i-mid)/2) int x=i-mid+2*nexta2i; if(xans)ans=x; solve(a, mid-1); solve(a + mid, len-mid);int main() /freopen(a.txt,r,stdin); while(scanf(%s,a)!=EOF) ans=1; solve(a,strlen(a); printf(%dn,ans); Timus 1297 最长回文子串后缀数组解法Time Limit: 1.0 secondMemory Limit: 16 MBThe “U.S. Robots” HQ has just received a rather alarming anonymous letter. It states that the agent from the competing Robots Unlimited has infiltrated into “U.S. Robotics”. U.S. Robots security service would have already started an undercover operation to establish the agents identity, but, fortunately, the letter describes communication channel the agent uses. He will publish articles containing stolen data to the “Solaris” almanac. Obviously, he will obfuscate the data, so “Robots Unlimited” will have to use a special descrambler (“Robots Unlimited” part number NPRx8086, specifications are kept secret).Having read the letter, the “U.S. Robots” president recalled having hired the “Robots Unlimited” ex-employee John Pupkin. President knows he can trust John, because John is still angry at being mistreated by “Robots Unlimited”. Unfortunately, he was fired just before his team has finished work on the NPRx8086 design. So, the president has assigned the task of agents message interception to John. At first, John felt rather embarrassed, because revealing the hidden message isnt any easier than finding a needle in a haystack. However, after he struggled the problem for a while, he remembered that the design of NPRx8086 was still incomplete. “Robots Unlimited” fired John when he was working on a specific module, the text direction detector. Nobody else could finish that module, so the descrambler will choose the text scanning direction at random. To ensure the correct descrambling of the message by NPRx8086, agent must encode the information in such a way that the resulting secret message reads the same both forwards and backwards.In addition, it is reasonable to assume that the agent will be sending a very long message, so John has simply to find the longest message satisfying the mentioned property.Your task is to help John Pupkin by writing a program to find the secret message in the text of a given article. As NPRx8086 ignores white spaces and punctuation marks, John will remove them from the text before feeding it into the program.InputThe input consists of a single line, which contains a string of Latin alphabet letters (no other characters will appear in the string). String length will not exceed 1000 characters.OutputThe longest substring with mentioned property. If there are several such strings you should output the first of them.SampleinputThesampletextthatcouldbereadedthesameinbothordersArozaupalanalapuazorAoutputAroz