Gravatar
Dy
积分:4
提交:2 / 3

Pro1570  [POJ 3461] 乌力波

//这是我提交AC的第一道题

//庆祝一下写一篇题解~有什么不对欢迎提出

//一道经典的kmp题,一定要记住模版

//每一次询问时间复杂度大约O(n)的,使用O2评测机不会超时的哦

#include<iostream>
#include<iomanip>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<vector>
#include<cstring>
#include<map>
#include<set>
#include<queue>
#include<ctime>
#include<deque>
#include<list>
#include<stack>
#include<utility>
#define MAXN 1919810
#define ite iterator
#define fs fixed<<setprecision
typedef long long ll;
using namespace std;

inline ll read(){ll x=0,f=1;char z;z=getchar();while(z<'0'||z>'9'){if(z=='-')f=-1;z=getchar();}while(z>='0'&&z<='9')x=x*10+z-'0',z=getchar();return x*f;}
inline void write(ll x){if(x<0){x=-x;putchar('-');}if(x>9){write(x/10);}putchar(x%10+'0');}
//快读,快写,利用getchar()与putchar()比cin,cout快的特性
char p1 , p2;
int l1 , l2;
char str1[MAXN] , str2[MAXN];
int k[MAXN*2];

inline int solve(){
	memset(k , 0 , sizeof(k));//初始化数组
	int ans = 0;//答案
	register int x = 0;//以下是kmp的模版,比常规暴力时间更少
	for(register int i = 2 ; str2[i] ; ++i){
		while(x && str2[x+1] != str2[i])
			x = k[x];
		if(str2[x+1] == str2[i])
			++x;
		k[i] = x;
	}
	x = 0;
	for(register int i = 1 ; str1[i] ; ++i){
		while(x>0 && str2[x+1] != str1[i]){
			x = k[x];
		}
		if(str2[x+1] == str1[i]){
		}
		if(x == strlen(str2+1)){
			ans++;
			x = k[x];
		}
	}
	return ans;
}



int main(){
	
	freopen("oulipo.in" , "r" , stdin);
	freopen("oulipo.out" , "w" , stdout); 
	int n;
	n = read();
	//常规输入
	for(register int i = 1 ; i <= n ; ++i){
		memset(str1 , 0 , sizeof(str1));
		memset(str2 , 0 , sizeof(str2));
		scanf("%s" , str2+1);//下标从一开始
		scanf("%s" , str1+1);//格式化输入输出一定要学会。不喜欢的可以用cin更方便
		write(solve());
		putchar('\n');
	}
	
	return 0;
}

祝大家能顺利的通过每一场比赛!早日夺得noi金牌!加油!



2023-08-18 22:19:53    
我有话要说
暂无人分享评论!