點(diǎn)擊打開鏈接

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

題意：給一個(gè)原串給一個(gè)匹配串，匹配串可以任選一些不相鄰的字符，把這些字符和相鄰的字符交換，匹配成功串首為1，else0；

解：標(biāo)程用的bitset,不曉得是什么阿..暴力如下：

<pre name="code" class="cpp"> #include <iostream> #include <cstdio> #include <cstring> #include <string> #include <algorithm>using namespace std;char ans[100000 + 5];int main() {int t;cin>>t;while(t--){int n,m;cin>>n>>m;string a, b;cin>>a>>b;memset(ans, '1', sizeof ans);for(int i = 0; i <= n-m; i++){for(int j = 0; j < m; j++){if(a[i+j] == b[j]);else if(j < m-1 && a[i+j] == b[j+1] && a[i+j+1] == b[j]) // 交換匹配，先控制范圍j++;else{ans[i] = '0';break;}}}for(int i = 0; i < n-m+1; i++)cout<<ans[i];while(--m)cout<<'0'; //倒數(shù)幾個(gè)長度不夠的一定匹配不到。cout<<endl;}return 0;}

總結(jié)

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

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