【PTA】7-4 统计子串

编写算法，统计子串t在主串s中出现的次数。

输入格式:

首先输入一个整数T，表示测试数据的组数，然后是T组测试数据。每组测试数据在第一行中输入主串s，在第二行中输入子串t，s和t中不包含空格。

输出格式:

对于每组测试，若子串t在主串s中出现，则输出t在s中的子串位置和出现总次数，否则输出0 0。

输入样例:

2
abbbbcdebb
bb
abcde
bb

输出样例:

2 4
0 0

来源：

[1] 黄龙军, 等. 数据结构与算法, 上海:上海交通大学出版社, 2022.7. ISBN: 9787313269881
[2] 黄龙军, 等. 数据结构与算法（Python版）,上海: 上海交通大学出版社, 2023. ISBN: 9787313280732

代码长度            16 KB
时间               400 ms
内存                 MB
栈                8192 KB

代码:(C语言，运用顺序串）

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

typedef struct SString
{
    char ch[100005];//提示：数组设大一点，不然会答案错误
    int length;
}SString;

void StrAssign(SString *T);
int GetLength(SString *S);
void StrOutput(SString *T);//串输出
void get_next(SString *T,int next[]);
int Index_KMP(SString *S,SString *T,int next[]);


int main()
{
    SString T,S;

    int n,i,p;
    int next[100005];//提示：数组设大一点，不然会答案错误
    
    scanf("%d\n",&n);//循环次数
    for(i=1;i<=n;i++)
    {
        StrAssign(&T);
        StrAssign(&S);
//        StrOutput(&T);//判断是否正确输入，输出出来看看
//        StrOutput(&S); //判断是否正确输入，输出出来看看

        get_next(&S,next);
        p=Index_KMP(&T,&S,next);
        if(p==0)
            printf("0 ");
       
        printf("%d\n",p);
        
    }
    
}

int GetLength(SString *S)
{
    int cnt=0;
    int i=1;

    while(S->ch[i]!='\0')
    {
        i++;
        cnt++;
    }

    return cnt;
}

void StrAssign(SString *T)//串输入
{
    scanf("%s",&T->ch[1]);
    T->length=GetLength(T);
}

void StrOutput(SString *T)//串输出
{
    int i;
    for(i=1;i<=T->length;i++)
    {
        printf("%c",T->ch[i]);
    }
    printf("\n");
}

void get_next(SString *T,int next[])
{
    int i=1;int j=0;
    next[1]=0;
    while(i<T->length){
        if(j==0 || T->ch[i]==T->ch[j]){
            ++i;
            ++j;
            if(T->ch[i]!=T->ch[j])
                next[i]=j;
            else
                next[i]=next[j];
            next[i]=j;
        }
        else{
            j=next[j];
        }
    }
}


int Index_KMP(SString *S,SString *T,int next[])
{
    int i,j=1;
    int p=0;;
    int pos=1;
    for(i=pos;i<=S->length;)
    {
        if(j==0 || S->ch[i]==T->ch[j])
        {
            i++;
            j++;
        }
        else
        {
            j=next[j];
        }
    
    if(j>T->length)
    {
    	if(p==0)
	        printf("%d ",i-T->length);
        p++;
        j=1;
        pos=i-T->length+1;
        i=pos;
    }
    }
    return p;

}

运行结果：