【CSU-1598】解题报告（KMP）

原始题目

1598: 最长公共前缀

  • Time Limit: 1 Sec
  • Memory Limit: 128 Mb
  • Submitted: 222
  • Solved: 186

Description

给定两个字符串\(s\)和\(t\)，现有一个扫描器，从\(s\)的最左边开始向右扫描，每次扫描到一个\(t\)就把这一段删除，输出能发现\(t\)的个数。 ### Input 第一行包含一个整数$ T ( T 50)$ ，表示数据组数。 每组数据第一行包含一个字符串\(s\)，第二行一个字符串\(t\)，字符串长度不超过\(1000000\)。

Output

对于每组数据，输出答案。

Sample Input

2
ababab
ab
ababab
ba
Sample Output
3
2

Hint

Source

国防科学技术大学第十八届银河之光文化节ACM程序设计竞赛初赛

题目大意

如题 # 解题思路 - 加一个\(Next[m]=0\)即匹配完成后删除这一段（去重） - 不过这个题目水，不加也过了

解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
//#include <bits/stdc++.h>
#include <cstdio> 
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <iomanip>
#include <string>
#include <map>
#include <set>
#include <algorithm>
#include <queue>
#include <vector>
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
#define PI acos((double)-1)
#define E exp(double(1))
#define K 1000000+9
#define rep(i,a,n) for(int i=a;i<n;i++)
#define per(i,a,n) for(int i=n-1;i>=a;i--)
#define ms(x,a) memset((x),(a),sizeof(a))
int nt[10006];
char a[K],b[10005];
int n,m;
//参数为模板串和next数组
//字符串均从下标0开始
void kmpGetNext(char *s,int *Next)
{
    Next[0]=0;
    int len=strlen(s);
    for(int i=1,j=0;i<len;i++)
    {
        while(j&&s[i]!=s[j]) j=Next[j];
        if(s[i]==s[j]) j++;
        Next[i+1]=j;
    }
    Next[len]=0;
}
int kmp(char *ss,char *s,int *Next)
{
    kmpGetNext(s,Next);
//  调试输出Next数组
//	int len=strlen(s);
//	for(int i=0;i<=len;i++)
//		cout<<Next[i]<<" ";
//	cout<<endl; 

    int ans=0;
    int len1=strlen(ss);
    int len2=strlen(s);
    for(int i=0,j=0;i<len1;i++)
    {
        while(j&&ss[i]!=s[j])j=Next[j];
        if(ss[i]==s[j]) j++;
        if(j==len2){
        	ans++;
//			return i-len2+2;
		}
           
    }
//    return -1;
	return ans;
}

int main(void)
{
//	ios::sync_with_stdio(false);
    int t;
    scanf("%d",&t); 
    while(t--)
    {
    	memset(a,0,sizeof(a));
    	memset(b,0,sizeof(b));
    	scanf("%s",a);
    	scanf("%s",b);
    	cout<< kmp(a,b,nt)<<endl;
    }

    return 0;
}

收获与反思

  • KMP水题