[Hiho]1015-KMP算法

題目：

輸入

第一行一個整數N，表示測試資料組數。

接下來的N*2行，每兩行表示一個測試資料。在每一個測試資料中，第一行為模式串，由不超過10^4個大寫字母組成，第二行為原串，由不超過10^6個大寫字母組成。

其中N<=20

輸出

對于每一個測試資料，按照它們在輸入中出現的順序輸出一行Ans，表示模式串在原串中出現的次數。

Sample Input

5
HA
HAHAHA
WQN
WQN
ADA
ADADADA
BABABB
BABABABABABABABABB
DAD
ADDAADAADDAAADAAD
           

Sample Output

3
1
3
1
0
           

Solution:

需要稍加改造KMP算法，因為有重疊的現象，是以需要将模式串的next數組往後再計算一位，比如ADA,首尾是一樣的，那就計算ADAX，X所在next數，這樣重疊現象也可解決。

#include<iostream>
#include<string>

using namespace std;
int * BuildNext(string pattern)
{
    int n = pattern.size();
    int* next = new int[n+];
    int k = -;
    next[] = -;
    int j = ;
    while(j < n)
    {
        if(k == - || pattern[j] == pattern[k])
        {
            k++;
            j++;
            if( j == n || pattern[j] != pattern[k])
            {
                next[j] = k;
            }
            else
                next[j] = next[k];
        }
        else
            k  = next[k];
    }

    return next;
}

int Search(string pattern,string original)
{

    int n = original.size();
    int *next = BuildNext(pattern);
    int j = ;
    int count = ;
    for(int i = ;i<original.size();i++)
    {
        if(j >  && pattern[j] != original[i])
        {
            j = next[j];
            if(j == -)
                 j = ;
        }
        if(pattern[j] == original[i])
            j++;
        if(j == pattern.size())
        {
            count++;
            j = next[j];
            if(j == -)
                j = ;
        }
    }

    return count;
}


int main()
{
    char rows;
    int row = ;
    int i,j,k;
    i = j = k = ;
    cin>>row;
    string* pattern = new string[row];
    string* original = new string[row];
    for(i = ;i<row;i++)
    {
            cin>>pattern[i];
            cin>>original[i];
    }
    for(i = ;i<row;i++)
    {
        int count  = Search(pattern[i],original[i]);
        cout<<count<<endl;
    }
    return ;
}