La Vie en rose

Time Limit: 14000/7000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 643 Accepted Submission(s):
328

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

4 1

abac

4 2

aaaa

9 3

abcbacacb

abc

Sample Output

1010

1110

100100100

Author

zimpha

题意：输入两个字符串s串和p串，p串从s串的第一个字符开始一直比较到最后一个（如果后面字符比p串段，则肯定输出0），比较的时候若不相同，则p串的字符可以相邻交换进行比较，每个位置只能交换一次，（只是当前比较的交换，而不是永久交换），相同字符串输出1，不同则输出0。

纯暴力，从第一个字符开始比较就好。

附上代码：

 #include <iostream>

 #include <cstdio>

 #include <cmath>

 #include <cstring>

 #define  ll long long

 using namespace std;

 char s1[],s2[];

 int main()

 {

     int T,i,j;

     scanf("%d",&T);

     while(T--)

     {

         int len1,len2;

         memset(s1,'\0',sizeof(s1));

         memset(s2,'\0',sizeof(s2));

         scanf("%d%d",&len1,&len2);

         scanf("%s%s",s1,s2);

         char w;

         if(len1<len2)

         {

             for(i=; i<len1; i++)

                 printf("");

             printf("\n");

             continue;

         }

         for(i=; i<len1; i++)

         {

             int t=;

             for(j=i; j<i+len2&&j<len1; j++)

             {

                 if(s1[j]!=s2[t])

                 {

                     if(j==i+len2-)

                         break;

                         if(s1[j+]!=s2[t]||s1[j]!=s2[t+])

                             break;

                         else

                         {

                             t+=;

                             j+=;

                         }

                 }

                 else

                 {

                     t++;

                 }

             }

             if(j==i+len2)

                 printf("");

             else

                 printf("");

         }

         printf("\n");

     }

     return ;

 }

巴特西

hdu 5745 La Vie en rose（2016多校第二场）

La Vie en rose

最新文章

热门文章