Cod sursa(job #2352292)

Utilizator _Victor_Victor Ciobanu _Victor_ Data 23 februarie 2019 10:48:39
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.64 kb
#include <bits/stdc++.h>
#define MAXN 2000010
using namespace std;
 
string A,B;
int Pa[MAXN],P[MAXN];
 
int main(){
	ifstream cin("strmatch.in");
	ofstream cout("strmatch.out");
	cin>>A>>B;
	for(int i=1;i<A.size();i++){
		if(A[i]==A[0]){
			int j=0;
			while(i+j<A.size() && A[i+j]==A[j]){
				Pa[i+j]=++j;
			}
			i+=j;
		}
	}
	int j=0,i=0,l=0;
	while(i<B.size()){
		if(A[j]==B[i]){
			i++;
			j++;
		}
		if(j==A.size()){
			P[l++]=i-j;
			j=Pa[j-1];
		}else if(i<B.size() && A[j]!=B[i]){
			if(j!=0)j=Pa[j-1];
			else i++;
		}
	}
	cout<<l<<'\n';
	//l=min(l,1000);
	for(int i=0;i<l && i<1000;i++)cout<<P[i]<<' ';
}