Cod sursa(job #2352287)

Utilizator _Victor_Victor Ciobanu _Victor_ Data 23 februarie 2019 10:45:11
Problema Potrivirea sirurilor Scor 38
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.65 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;
	int i=1,j=0;
	while(i<A.size()){
		while(A[i]==A[j]){
			j++;
			Pa[i]=j;
			i++;
		}
		if(i<A.size()){
			if(j){
				j=Pa[j-1];
			}else{
				j=0;
				i++;
			}
		}
	}
	int l=0;
	i=j=0;
	while(i<B.size()){
		while(A[j]==B[i]){
			i++;
			j++;
		}
		if(j==A.size()){
			P[l++]=i-j;
			j=Pa[j-1];
		}else if(i<B.size()){
			if(j!=0)j=Pa[j-1];
			else i++;
		}
	}
	cout<<l<<'\n';
	l=min(l,1000);
	for(int i=0;i<l;i++)cout<<P[i]<<' ';
}