KMP

优化失配函数

#include <bits/stdc++.h>
#define mem(ar,num) memset(ar,num,sizeof(ar))
#define me(ar) memset(ar,0,sizeof(ar))
#define lowbit(x) (x&(-x))
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
const int    prime = 999983;
const int    INF = 1e8;
const LL     INFF =0x7FFFFFFFFFFFFFFF;
const double pi = acos(-1.0);
const double inf = 1e18;
const double eps = 1e-6;
const int maxn = 1e5+100;
int f[maxn],f2[maxn];
char ch[4][maxn];
char pro[maxn];
int Min[maxn];
int ans[maxn];
int q[maxn];
int LEN[4];
#define Checkmin(a,b) (a > b?a = b:1)
void getFail(char *P, int *f,int m)
{
//    int m = strlen(P);
    f[0] = f[1] = 0;
   f2[0]=f2[1]=0;
    for(int i = 1; i < m; i++)
    {
        int j = f2[i];
        while(j && P[i] != P[j] ) j = f2[j];
        f2[i+1] = f[i + 1] = (P[i] == P[j]) ? j + 1 : 0;

        //既然i+1的失配位置指向j+1，但是P[i+1]和P[j+1]的内容是相同的
        //所以就算指针从i+1跳到j+1去，还是不能匹配，所以f[i+1]直接=f[j+1]
        if(f[i+1]==j+1 && P[i+1]==P[j+1]) f[i+1]=f[j+1];
    }
}
int n,len;

void Find(char *T,char * P,int* f,int *M,int num)
{
    int n = len,m = LEN[num];
    getFail(P,f,m);
    int j = 0;
    int l = 0,r = 0;
    q[0] = 0;
    for(int i =  0;i < n; ++i)
    {
        if(T[i] == '-'){
            if(r > l ) r--;
            j = q[r];
        }
        else
       {
         while(j&&P[j] != T[i]) j = f[j];
         if(P[j] == T[i]) j++;
         q[++r] = j;
       }
        Checkmin(M[i],m-q[r]);
//        if(j == m) printf("%d\n",i-m+1);
    }
}

int main(void)
{

    scanf("%d",&n);
    int t = INF;
    for(int i = 0;i < n; ++i) scanf("%s",ch[i]),LEN[i] = strlen(ch[i]),t = min(t,LEN[i]);
    scanf("%s",pro);
    len = strlen(pro);
//    memset(Min,0xfffffffff,sizeof(Min));
    fill(Min,Min+len,INF);
    for(int i = 0;i < n; ++i)
      {
         Find(pro,ch[i],f,Min,i);
      }
    printf("%d\n",t);
    for(int i = 0;i < len; ++i){
          printf("%d\n",Min[i]);
    }
    return 0;
}