Cod sursa(job #2352233)

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