首页 > 代码库 > 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;}