kmp模式匹配（统计子串t在主串s中出现的次数） （语言c++）

Question

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

#define OK 1
#define ERROR 0
#define OVERFLOW -2
typedef int Status;
#define MAXSTRLEN 255 

void get_nextval(char T[], int nextval[])
{ 
    int i = 1, j = 0;
    nextval[1] = 0;
    while (i < T[0])
        if (j == 0 || T[i] == T[j])
        {
            ++i;
            ++j;
            if (T[i] != T[j])
                nextval[i] = j;
            else
                nextval[i] = nextval[j];
        } 
        else
            j = nextval[j];
}

Status Index_KMP(char S[], char T[], int pos, int next[])
{ 
    int i = pos, j = 1;
    while (i <= S[0] && j <= T[0])
        if (j==0||S[i]==T[j]) 
        {
            ++i;
            ++j;
        }
        else
            j=next[j]; 
    if (j > T[0]) 
        return i-T[0];
    else
        return 0;
}

Status times(char S[], char T[])
{ 
    int i = 1, j = 1;
    int times = 0;
    int next[MAXSTRLEN];
    get_nextval(T,next);
    while (i <= S[0] && j <= T[0])
    {
        if (j==0||S[i]==T[j]) 
        {
            i++;
            j++;
        }
        else
            j=next[j]; 
        if (S[i]==T[j]&&j == T[0]) 
        {
            times++;
            j=0;
        }
    }
    return times;  
     
}

int main()
{
    int n;
    cin>>n;
    while(n--)
    {
        char S[MAXSTRLEN+1],T[MAXSTRLEN+1];
        char S1[MAXSTRLEN],S2[MAXSTRLEN];
        cin >> S1 >> S2;
        strcpy(&S[1],S1);
        strcpy(&T[1],S2);    
        S[0]=strlen(S1);
        T[0]=strlen(S2);
        int *p = new int[T[0]+1];
        get_nextval(T,p);
        cout<<Index_KMP(S,T,1,p)<<" "<<times(S,T)<<endl;
    }
    
    return 0;
}

能知道大概率是times++那部分if语句出了问题，但我不会改，求指教。

Answer 1

试试可以不

#include <string.h>
#include <iostream>

using namespace std;

#define OK 1
#define ERROR 0
#define OVERFLOW -2
typedef int Status;
#define MAXSTRLEN 255

void get_nextval(char T[], int nextval[]) {
    int i = 1, j = 0;
    nextval[1] = 0;
    while (i < T[0]) {
        if (j == 0 || T[i] == T[j]) {
            ++i;
            ++j;
            if (T[i] != T[j]) {
                nextval[i] = j;
            } else {
                nextval[i] = nextval[j];
            }
        } else {
            j = nextval[j];
        }
    }
}

Status Index_KMP(char S[], char T[], int pos, int next[]) {
    int i = pos, j = 1;
    while (i <= S[0] && j <= T[0]) {
        if (j == 0 || S[i] == T[j]) {
            ++i;
            ++j;
        } else {
            j = next[j];
        }
    }
    if (j > T[0]) {
        return i - T[0];
    } else {
        return 0;
    }
}

Status times(char S[], char T[]) {
    int i = 1, j = 1;
    int times = 0;
    int next[MAXSTRLEN];
    get_nextval(T, next);
    while (i <= S[0] && j <= T[0]) {
        if (j == 0 || S[i] == T[j]) {
            ++i;
            ++j;
        } else {
            j = next[j];
        }
        if (j > T[0]) {
            ++times;
            j = 1;
        }
    }
    return times;
}

int main() {
    int n;
    cin >> n;
    while (n--) {
        char S[MAXSTRLEN + 1], T[MAXSTRLEN + 1];
        char S1[MAXSTRLEN], S2[MAXSTRLEN];
        cin >> S1 >> S2;
        strcpy(&S[1], S1);
        strcpy(&T[1], S2);
        S[0] = strlen(S1);
        T[0] = strlen(S2);
        int* p = new int[T[0] + 1];
        get_nextval(T, p);
        cout << Index_KMP(S, T, 1, p) << " " << times(S, T) << endl;
        delete[] p;
    }
    return 0;
}