算法模版：KMP模板及字符串经典模拟

ne[j] 作用：记录模式串中 j 之前的最长的相等前后辍
这样当出现不匹配的时候后
可以直接跳转到 以前一个字符 结尾的 公共最长前后辍 的前缀 的后面
例如下面这个例子
 s：  abbabfab
 p：  abbabc
当前位置时
s串的'f'与p串的'c'不匹配
kmp的思想是：跳转到 以'c'前面的'b'字符结尾的 公共最长前后辍 的 前缀 的后面 
即 前缀 ab 后面 'b'位置
 s：  abbabfab
 p：   abbabc

#include<bits/stdc++.h>
using namespace std;
const int N = 1e7+10;
int n,m;
int ne[N];
char s[N],p[N];
int main()
{
  cin>>s+1>>p+1;
  n=strlen(s+1),m=strlen(p+1);
  生成 ne【】数组 ，这里利用了动态规划的思想
  for(int i =2 , j = 0 ;  i <= m ; i ++)
  {
     while(j&&p[i]!=p[j+1])j=ne[j];
     if(p[i]==p[j+1])j++;
     ne[i]=j;
  }
  利用ne【】数组，增强匹配效率
  for(int i = 1 , j = 0; i <= n ; i ++)
  {
    while(j&&s[i]!=p[j+1])j=ne[j];
    if(s[i]==p[j+1])j++;
    if(j==m)
    {
      printf("%d\n",i-m+1);
      j=ne[j];
  }
  for(int i = 1 ; i <= m ; i ++)
  printf("%d ",ne[i]);
}

#include<bits/stdc++.h>
using namespace std;
const int N = 1e7+10;
int n,m;
int ne[N];
char s[N],p[N];
void kmp(int n,string a,string b)
{
  for(int i = 0 ; i < n ; i ++)
  {
  int j = 0 ,k=i;
  while(a[k++]==b[j++]&&a[k-1]!=0)continue;
  if(j==b.size()+1)
  {
    cout<<b+" is substring of "+a;
    return ; 
  }
  }
  cout<<"No substring";
  return ;
}
int main()
{
   string a,b;
   cin>>a>>b;
   if(a.size()>b.size())
   kmp(a.size(),a,b);
   else
   kmp(b.size(),b,a);
}

#include<stdio.h>
#include<string.h>
int main()
{
  int i,j,m,n;
  char a[100];
  gets(a);
  n=strlen(a);
  if(a[n-2]=='e'&&a[n-1]=='r')
  a[n-2]=0;
  else if(a[n-3]=='i'&&a[n-2]=='n'&&a[n-1]=='g')
  a[n-3]=0; 
  else if(a[n-2]=='l'&&a[n-1]=='y')
  a[n-2]=0;
  printf("%s",a);
  return 0;
}

while（cin>>a）

#include<bits/stdc++.h>
using namespace std;
int ans,cnt=99999;
int main()
{
  string a,b,c;
  while(cin>>a)
  {
  if(a.size()>ans) 
  {
    b=a;
    ans=a.size();
  }
  if(a.size()<cnt)
  {
    c=a;
    cnt=a.size();
  }
  }
  cout<<b<<"\n"<<c;
  return 0;
}

hello world

hello world

#include<bits/stdc++.h>
using namespace std;
int main()
{
  string a,b;
  getline(cin,a);
  for(int i = 0; i <= a.size(); i ++)
  {
  if(a[i]==' '||a[i]==0)
  {
    for(int j = i-1;a[j]!=' '&&j>=0; j --)
    cout<<a[j];
    cout<<" ";
  }
  }
  return 0;
}