记录编号	581842	评测结果	AAA
题目名称	[POJ 3461] 乌力波	最终得分	100
用户昵称	Dy	是否通过	通过
代码语言	C++	运行时间	0.290 s
提交时间	2023-08-18 21:51:41	内存使用	24.04 MiB

#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');}

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;
	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;
//	cout << ".........";
//	for(register int i = 0 ; i <= 9 ; ++i){
//		cout << k[i] << "  ";
//	}cout << endl;
//	register int i;
//	cout << "===" << i << endl;
//	for(register int i = 1 ; str2[i] ; ++i){
//		cout << k[i] << "  ";
//	}cout << endl;
//	cout << "++++++" << x << endl;
	for(register int i = 1 ; str1[i] ; ++i){
//		cout << "+++++++++" << x << endl; 
		while(x>0 && str2[x+1] != str1[i]){
//			cout << "====" << x << endl;
//			cout << "-----" << (int)str2[x+1] << "   " << str1[i] << endl;
			x = k[x];
//			cout << "+++++++" << x << endl;
		}
//		for(register int a = 1 ; str1[a] ; ++a){
//			cout << "_____" << str1[a] << " ";
//		}cout << endl;
//		for(register int a = 1 ; str2[a] ; ++a){
//			cout << "_____" << str2[a] << " ";
//		}cout << endl;
			
		if(str2[x+1] == str1[i]){
			++x;
//			cout << "______" << str2[x] << "   " << str1[i] << endl;
//			cout << "||||||->" << x << endl;
		}
		if(x == strlen(str2+1)){
//			cout << "------=======" << x << endl;
//			cout << "======-------" << strlen(str2+1) << endl;
//			write(i - x + 1);
//			printf("\n");
			ans++;
//			cout << "________________" << x << endl;
			x = k[x];
		}
//		cout << "   " << x << endl;
	}
	return ans;
//	for(register int i = 1 ; str2[i] ; ++i)
//		cout << k[i] << ' ';
}



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);
	cout << solve() << endl;
	}
//	for(register int i = 1 ; 	str1[i] ; ++i)
//		cout << str1[i] << " ";
//	cout << "\n";
//	for(register int i = 1 ; str2[i] ; ++i)
//		cout << str2[i] << " ";
//	cout << "\n";
	
//	cout << "----" << strlen(str1+1) << "   " << strlen(str2+1) << endl;
	
	
	
	return 0;
}