題目鏈接：HDU 5745

題面：

La Vie en rose

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


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

題意：

??? 問給定一個原串，一個模式串，原串任意位置的一段連續(xù)子串是否能通過交換任意相鄰兩位得到，可以則輸出1，不可以則輸出0。

解題：

??? 這題，純暴力就能過，復雜度看似懸，但很難出數(shù)據(jù)卡住，或者可以理論上證明，是卡不住的，加一個前綴和的預判，大概能優(yōu)化1s。如果，當前位和模式串位不同，只能和后一位交換，此時下標加2，若不能交換，則代表不行。

代碼：

#include <iostream> #include <cstring> #include <cstdio> #define LL long long #define sz 100005 using namespace std; char s[sz],p[5005]; int num[sz][26],cnt[26]; int n,m; int main() {int t,n,m;bool flag;scanf("%d",&t);while(t--){scanf("%d%d",&n,&m);scanf("%s",s);scanf("%s",p);memset(cnt,0,sizeof(cnt));for(int i=0;i<26;i++)num[0][i]=0;for(int i=1;i<=n;i++){for(int j=0;j<26;j++)num[i][j]=num[i-1][j];num[i][s[i-1]-'a']++;}for(int i=0;i<m;i++)cnt[p[i]-'a']++;for(int i=0;i<=n-m;i++){ flag=1;for(int j=0;j<26;j++){if(cnt[j]!=num[i+m][j]-num[i][j]){flag=0;break;}}if(flag){for(int j=0;j<m;j++){if(s[i+j]==p[j])continue;else{if(j==m-1){flag=0;break;}if(s[i+j]==p[j+1]&&s[i+j+1]==p[j]){j++;}else{flag=0;break;}}}}if(flag)printf("1");elseprintf("0");}for(int i=1;i<m;i++)printf("0");printf("\n");}return 0; }

總結

以上是生活随笔為你收集整理的HDU 5745 La Vie en rose(简单模拟)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。