题解 第四章字符串|#Number Sequence#

王道P55KMP算法

#include <stdio.h>
#include <iostream>
using namespace std;

void getNextval(int Mode[], int Nextval[], int Mode_Num)
{
    //标出初始状态
    int i = 0, j = -1;
    int Next[Mode_Num];
    Next[0] = -1, Nextval[0] = -1;
    //求Next和Nextval数组
    while (i < Mode_Num)
    {
        if (j == -1 || Mode[i] == Mode[j])
        {
            Next[++i] = ++j;
            //根据刚求出的Next数组值计算Nextval数组值
            if (Mode[j] == Mode[Next[j]])
                Nextval[i] = Nextval[Next[i]];
            else
                Nextval[i] = Next[i];
        }
        else
            j = Next[j];
    }
}

void KMP_Multi(int CArr[], int Mode[], int P[], int CArr_Num, int Mode_Num)
{
    int Nextval[Mode_Num];
    getNextval(Mode, Nextval, Mode_Num);

    int i = 0, j = 0;
    int R = 0;
    while (1)
    {
        while (i < CArr_Num && j < Mode_Num)
        {
            if (j == -1 || CArr[i] == Mode[j])
                i++, j++;
            else
                j = Nextval[j];
        }
        if (j == Mode_Num)
        {
            P[R++] = i - j;
            i = i - j + 1;
            j = 0;
        }
        else
        {
            P[R] = -1;
            break;
        }
    }
}

int main()
{
    //输入组数
    int Case_Num = 0;
    scanf("%d", &Case_Num);

    while (Case_Num--)
    {
        //以下即将所有数组输入
        int CArr_Num = 0, Mode_Num = 0;
        scanf("%d%d", &CArr_Num, &Mode_Num);
        int CArr[CArr_Num];
        int Mode[Mode_Num];
        for (int i = 0; i < CArr_Num; i++)
            scanf("%d", &CArr[i]);
        for (int i = 0; i < Mode_Num; i++)
            scanf("%d", &Mode[i]);

        //采用KMP算法,找出所有的匹配位置,并存入P数组
        int P[CArr_Num];
        KMP_Multi(CArr, Mode, P, CArr_Num, Mode_Num);
        printf("%d\n", P[0]);
    }
    return 0;
}
/*输入
2
13 5
1 2 1 2 3 1 2 3 1 3 2 1 2
1 2 3 1 3
*/
/*输出
5
*/
/*输入
13 5
1 2 1 2 3 1 2 3 1 3 2 1 2
1 2 3 2 1
*/
/*输出
-1
*/