小明的字符串（蓝桥杯）

题目描述
小明有两个字符串，分别为 S,T。

请你求出 TT 串的前缀在 S 串中出现的最长长度为多少。

输入描述
输入包含两行，每行包含一个字符串，分别表示 S,T。

1 < |S|,|T| < 10^6 ，保证 S,T 只包含小写字母。

输出描述
输出共 1 行，包含一个整数，表示答案。

输入输出样例
示例 1

输入

aabba

abb

输出

3

示例 2

输入

aabba

aba

输出

2

KMP写法

#include<iostream>
using namespace std;
char s1[105],s2[105];
int ne[105];
int main()
{
  scanf("%s",s1+1);
  scanf("%s",s2+1);
  int k1=1,k2=1;
 while(s1[k1++]!='\0') ;k1--;
 while(s2[k2++]!='\0') ; k2--;
 for(int i=2,j=0;i<=k2;i++)
 {
   while(j&&s2[i]!=s2[j+1]) j=ne[j];
   if(s2[i]==s2[j+1]) j++;
   ne[i]=j;
 }
 int max_=0;
 for(int i=1,j=0;i<=k1;i++)
 {
   while(j&&s1[i]!=s2[j+1]) j=ne[j];
   if(s1[i]==s2[j+1])
   {
     j++;
     if(max_<j) max_=j;
     if(j==k2)
     {
       cout<<k2;
       return 0;
     }
     
   }
 }
 cout<<max_;
}