Cod sursa(job #2352218)

Utilizator _Victor_Victor Ciobanu _Victor_ Data 23 februarie 2019 09:46:27
Problema Potrivirea sirurilor Scor 16
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.67 kb
#include <bits/stdc++.h>
#define MAXN 2000010
using namespace std;

string A,B;
vector <int> P;
int Pa[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;
	for(int i=0;i<B.size();i++){
		if(A[0]==B[i]){
			while(j<A.size() && i+j<B.size() && A[j]==B[i+j]){
		 		j++;
		 	}
		 	if(j==A.size())P.push_back(i);
		 	j--;
			if(j>0 && Pa[j]){
		 		i+=j-1;
		 		j=Pa[j]-1;	
			}else j=0;
		}
	}
	cout<<P.size()<<'\n';
	for(int i=0;i<P.size();i++)cout<<P[i]<<' ';
}