首页 > 代码库 > UVa10340
UVa10340
All in All
题意:字符串匹配
#include <stdio.h>#include <string.h>char S[200000];char P[200000];int next[200000];int KMP(int pos, int len1, int len2){ int i = pos, j = 1, k = 0; next[1] = 0; while (j < len1) if (k == 0 || P[k - 1] == P[j - 1]) j++, k++, next[j] = k; else k = next[k]; j = 1; while (i <= len2 && j <= len1) { if (j == 0 || S[i - 1] == P[j - 1]) i++, j++; else j = next[j]; } return j > len1 ? i - len1 : 0;}int main(int argc, char *argv[]){ int len1, len2, i, t1, t2, j, b, c; while(scanf("%s%s", P, S) != EOF) { t1 = t2 = 1; b = -1; len1 = strlen(S); len2 = strlen(P); if(KMP(0, len2, len1) == 0) t2 = 0; if(t2 == 0) { for(i = 0; i < len2; i++) { c = 0; for(j = 0; j < len1; j++) { if(P[i] == S[j] && b < j) { b = j; c = 1; break; } } if(c != 1) t1 = 0; } } printf("%s\n", t1 || t2 ? "Yes" : "No"); memset(S, 0, sizeof(S)); memset(P, 0, sizeof(P)); memset(next, 0, sizeof(next)); } return 0;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。