杭电OJ 5745 La Vie en rose
La Vie enrose
Problem Description
Professor Zhangwould like to solve the multiple pattern matching problem, but he only has onlyone pattern string p=p1p2...pm. So, he wants to generate as many as possible patternstrings from p using the following method:
1. select some indices i1,i2,...,ik such that 1≤i1
Now, for a given a string s=s1s2...sn, Professor Zhang wants to find all occurrences of allthe generated patterns in s.
Input
There are multipletest cases. The first line of input contains an integer T, indicating the number of test cases. For each testcase:
The first line contains two integers n and m (1≤n≤105,1≤m≤min{5000,n}) -- thelength of s and p.
The second line contains the string s and thethird line contains the string p. Both the stringsconsist of only lowercase English letters.
Output
For each testcase, output a binary string of length n. The i-th character is "1" if and only if thesubstring sisi+1...si+m?1 is one ofthe generated patterns.
Sample Input
3
4 1
abac
a
4 2
aaaa
aa
9 3
abcbacacb
abc
Sample Output
1010
1110
100100100
解题思路：
这道题读起来很晦涩，光读懂就花了好长时间，不过其实题意很简单，就是定义了一个对字符串P的一个变换，选定若干个位置（这些位置至少间隔一个字符），然后在这些位置上与后一个相邻位置的字符进行交换，得到一个新的字符串。
此题的核心就是给定长度为m的字符串p，判断一个长度也为m的字符串q能否由字符串p通过上述变换得到的，只要设计出这样的判定算法，此题就迎刃而解。
对于字符串p = p1 p2p3 p4…pm和字符串q = q1 q2 q3…qm，如果两者可以通过题中给出的变换互相转化，对于字符串中任意的位置i (1<=i
输入字符串p和q（长度均为m，下标从0到m-1）
pos= 0
while pos < m
if q[pos] == p[pos]
pos++
else if q[pos] == p[pos+1] 且q[pos+1] == p[pos]
pos+= 2
else
【杭电OJ 5745 La Vie en rose】return false
return true
#include
#define SIZE 100100int main()
{
int T, n, m, i, pos1, pos2;
char s[SIZE], p[SIZE];
scanf("%d", &T);
while (T--) {
scanf("%d%d", &n, &m);
scanf("%s", s);
scanf("%s", p);
for (i = 0;
i <= n - m;
i++) {
pos1 = i;
pos2 = 0;
/*判断两个字符串是否可以通过题目中的变换相互转化*/
while (pos2 < m) {
if (s[pos1] == p[pos2]) {
pos1++;
pos2++;
}
else if(s[pos1] == p[pos2+1] && s[pos1+1] == p[pos2]) {
pos1 += 2;
pos2 += 2;
}
else
break;
}
if (pos2 == m)
printf("1");
else
printf("0");
}for (i = n-m+1;
i < n;
i++)
printf("0");
printf("\n");
} return 0;
}
推荐阅读
- 列出所有自定义的function和view
- 杭电oj——2030汉字统计
- tableView|tableView 头视图下拉放大 重写
- 记录iOS生成分享图片的一些问题，根据UIView生成固定尺寸的分享图片
- Flutter的ListView
- OC:|OC: WKWebView详解
- Swift|Swift ----viewController 中addChildViewController
- WKWebview|WKWebview js 调用oc 和oc调用js
- SwiftUI|SwiftUI iOS 瀑布流组件之仿CollectionView不规则图文混合(教程含源码)
- iview|iview upload 动态改变上传参数