這道題的官方題解是dp，但是可以暴力出來。改天再研究怎么dp。

暴力的時候，如果計算sum的時候，調用strlen函數會超時，可見這個函數并不是十分的好。以后能不用盡量不用。

?

La Vie en rose

Time Limit: 14000/7000 MS (Java/Others)????Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 861????Accepted Submission(s): 461

Problem Description Professor Zhang would like to solve the multiple pattern matching problem, but he only has only one pattern string?p=p1p2...pm. So, he wants to generate as many as possible pattern strings from?p?using the following method:

1. select some indices?i1,i2,...,ik?such that?1≤i1<i2<...<ik<|p|?and?|ij?ij+1|>1?for all?1≤j<k.
2. swap?pij?and?pij+1?for all?1≤j≤k.

Now, for a given a string?s=s1s2...sn, Professor Zhang wants to find all occurrences of all the generated patterns in?s.

?

Input There are multiple test cases. The first line of input contains an integer?T, indicating the number of test cases. For each test case:

The first line contains two integers?n?and?m?(1≤n≤105,1≤m≤min{5000,n})?-- the length of?s?and?p.

The second line contains the string?s?and the third line contains the string?p. Both the strings consist of only lowercase English letters.

?

Output For each test case, output a binary string of length?n. The?i-th character is "1" if and only if the substring?sisi+1...si+m?1?is one of the generated patterns.

?

Sample Input 3 4 1 abac a 4 2 aaaa aa 9 3 abcbacacb abc

?

Sample Output 1010 1110 100100100

?

Author zimpha

?

Source 2016 Multi-University Training Contest 2 #include<iostream> #include<stdio.h> #include<algorithm> #include<set> #include<map> #include<queue> #include<stack> #include<cmath> #include<cstring> #include<string> using namespace std; const int maxx=100005; int main(){int t;scanf("%d",&t);while(t--){int n,m;char s[maxx];char p[maxx];scanf("%d%d",&n,&m);scanf("%s",s);scanf("%s",p);int sump[maxx];int sums[maxx];sump[0]=sums[0]=0;for(int i=1;i<=n;i++){sums[i]=s[i-1]-'a'+sums[i-1];}for(int i=1;i<=m;i++){sump[i]=p[i-1]-'a'+sump[i-1];}int pis=sump[m];int shave=sums[m];for(int i=m;i<=n;i++){shave=sums[i]-sums[i-m];// cout<<"shave: "<<shave<<endl;if(pis==shave){int sta=i-m;int pos=sta;int flag=1;for(int j=0;pos<i;j++){if(s[pos]==p[j]){pos++;}else{if(pos+1<i&&s[pos+1]==p[j]&&s[pos]==p[j+1]){pos+=2;j++;}else{flag=0;break;}}}if(flag){printf("1");}else{printf("0");}}else{printf("0");}}for(int i=m-1;i>0;i--){printf("0");}printf("\n");}return 0; } View Code

?

轉載于:https://www.cnblogs.com/superxuezhazha/p/5697505.html

總結

以上是生活随笔為你收集整理的hdu 5745 la vie en rose的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。