题目

模式串可以浮动的模式匹配问题 给出模式串的相对大小，需要找出模式串匹配次数和位置 比如说模式串：1，4，4，2，3，1 而主串：5,6,2,10,10,7,3,2,9 那么2,10,10,7,3,2就是匹配的

首先是kmp的next数组求法

void_getnext(char x[], int m, int next[])
{
    int i, j;
    i = 0;
    j = next[0] = -1;
    while(i < m)
    {
        while(j != -1 && x[i] != x[j]) j = next[j];
        next[++i] = ++j;
    }
}

预处理每一位之前的每一种字符出现的次数。前缀和（还可以树状数组维护）

void init()
{
    for(int i=0;i<n;i++)
    {
        if(i==0)
        {
            for(int j=1;j<=25;j++)
                as[i][j]=0;
        }
        else
        {
            for(int j=1;j<=25;j++)
                as[i][j]=as[i-1][j];
        }
        as[i][a[i]]++;
    }
    for(int i=0;i<m;i++)
    {
        if(i==0)
        {
            for(int j=1;j<=25;j++)
                bs[i][j]=0;
        }
        else
        {
            for(int j=1;j<=25;j++)
                bs[i][j]=bs[i-1][j];
        }
        bs[i][b[i]]++;
    }
}

接下来求kmp中的next数组（需要求出j-i中比b[i]小的数的个数和与b[i]相同的数的个数 和 j之前比b[j]小的数的个数和与b[j]相同的数的个数 kmp基础思想）

void kmp_pre()           //处理出Next数组
{
    int i,j;
    j=Next[0]=-1;
    i=0;
    while(i<m)
    {
        int t11=0,t12=0,t21=0,t22=0;
        for(int k=1;k<b[i];k++)        // t11  从i往前j个牛有多少个比bi小的
        {
            if(i-j>0)
                t11+=bs[i][k]-bs[i-j-1][k];
            else
                t11+=bs[i][k];
        }
        if(i-j>0)                    // t22  从i往前j个牛，有多少个和bi一样的
            t12=bs[i][b[i]]-bs[i-j-1][b[i]];
        else
            t12=bs[i][b[i]];
        for(int k=1;k<b[j];k++)       //t21   第j头牛之前有多少个比bj小的
        {
            t21+=bs[j][k];
        }
        t22=bs[j][b[j]];               //t22   第j头牛之前有多少个和bj一样的
        if(j==-1 || (t11==t21 && t12==t22))    //转化为正常kmp思路
        {
            Next[++i]=++j;
        }
        else
            j=Next[j];
    }
}

接下来就是激动人心的匹配时间
正常的匹配代码：

int KMP_count(char x[], int m, char y[], int n)
{
    //预处理出char x[] 的next数组 preKMP(x,m,next);
    int i,j;  
    int ans = 0;     
    i = j = 0;
    //开始匹配
    while(i < n)
    {
        while(j != -1 && y[i] != x[j]) j = next[j];
        i++, j++;
        if(j >= m)
        {
            ans ++;
            j = mext[j];
        }
    }
    return ans;
}

这道题的kmp

void kmp()
{
    ans.clear();
    int i,j;
    kmp_pre();
    i=j=0;
    while(i<n)
    {
        //和kmppre一样的处理方法，计算小于本rank的和等于本rank的
        int t11=0,t12=0,t21=0,t22=0;
        for(int k=1;k<a[i];k++)
        {
            if(i-j>0)
                t11+=as[i][k]-as[i-j-1][k];
            else
                t11+=as[i][k];
        }
        if(i>j)
            t12=as[i][a[i]]-as[i-j-1][a[i]];
        else
            t12=as[i][a[i]];
        for(int k=1;k<b[j];k++)
        {
            t21+=bs[j][k];
        }
        t22=bs[j][b[j]];
        if(j==-1 || (t11==t21 && t12==t22))
        {
            i++;
            j++;
            if(j>=m)
            {
                ans.push_back(i-m+1);
                j=Next[j];
            }
        }
        else
            j=Next[j];
    }
}

然后本题就做完啦！