题目大意: 给两个串s1,s2。问s2能不能和s1循环移动n次(n>=0)的串中匹配成功。
解题思路: 硬模拟的话会超时,复杂度接近O(n^2)。由于循环移动之后的状态一定属于两个s1拼接后的其中一个字串。于是按此操作AC。复杂度O(2*n-1+m)。这题利用拼接的技巧似乎模式串匹配直接用strstr也能完成。效率也蛮高- - 。注意拼接字符串用strcat的时候不能用自己连接自己,会超时。
AC代码:
kmp:
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <iostream>
using namespace std;
#define MAXN 100001
char Tmp[200001],pattern[MAXN],T[MAXN];
int prefix[MAXN];
void get_prefix_table (int n) {
int i = 0, len = -1;
prefix[0] = -1;
while (i < n) {
if(len == -1 || pattern[i] == pattern[len]) {
i++;
len++;
prefix[i] = len;
}else {
len = prefix[len];
}
}
} // prefix保存到n,也就是整个串的前后缀都记录,长度为n+1。但如果整个串前后缀相同的字串长度为0,则这个不做记录!!! 在kmp中不可能索引到这个值
bool kmp_search (int n, int m) {
int i = 0, j = 0;
get_prefix_table (m);
while (i < n) {
if(j == -1 || Tmp[i] == pattern[j]) {
i++;
j++;
}else {
j = prefix[j];
}
if(j == m) {
return true;
}
}
return false;
}
int main() {
int n,m;
while (~scanf("%s%s", T, pattern)) {
strcpy(Tmp,T);
n = strlen(Tmp);
m = strlen(pattern);
if(m > n) {
printf("no\n");
continue;
}
strcat(Tmp,T);
if(kmp_search(2*n-1,m)) {
printf("yes\n");
}else {
printf("no\n");
}
}
return 0;
}
strstr:
#include<stdio.h>
#include<string.h>
int main()
{
char a[100001],b[100001],c[200001];
while(gets(a))
{
gets(b);
strcpy(c,a);
strcat(c,a);
if(strstr(c,b)!=NULL)
printf("yes\n");
else printf("no\n");
}
return 0;
}