数据结构实验之串二：字符串匹配

Description
给定两个字符串string1和string2，判断string2是否为string1的子串。

Input
输入包含多组数据，每组测试数据包含两行，第一行代表string1，第二行代表string2，string1和string2中保证不出现空格。(string1和string2大小不超过100字符)

Output
对于每组输入数据，若string2是string1的子串，则输出"YES"，否则输出"NO"。

Sample
Input

abc

a

123456

45

abc

ddd

Output

YES

YES

NO

Hint

#include<bits/stdc++.h>

using namespace std;
#define maxn 1000010

char s[maxn], p[maxn], Next[maxn];
void get_next()
{
   int j = -1, k = 0;
   Next[0] = -1;
   int len = strlen(p);
   while(k < len)
   {
       if(j == -1 || s[j] == s[k])
       {
           j++;
           k++;
           Next[k] = j;
       }
       else j = Next[j];
   }
}
int kmp()
{
   int i = 0, j = 0;
   int slen = strlen(s);
   int plen = strlen(p);
   while(i < slen && j < plen)
   {
       if(j == -1 || s[i] == p[j])
       {
           i++;
           j++;
       }
       else j = Next[j];
   }
   if(j == plen) return 1;
   else
       return 0;
}

int main()
{
   while(cin >> s)
   {
       cin >> p;
       get_next();
       if(kmp()) cout << "YES" << endl;
       else cout << "NO" << endl;
   }
   return 0;
}