Cod sursa(job #1923703)

Utilizator virtualityBbbbbbbbbbbbbbbbbb virtuality Data 11 martie 2017 22:00:23
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.57 kb
#include<bits/stdc++.h>
#define N 2000020
using namespace std;
string a, b;
int p[N], rez[N], sol;
int main(){
	int n, m;
	ifstream f("strmatch.in");
	ofstream g("strmatch.out");
	f>>b>>a;
	n=a.length();
	m=b.length();
	int i=1; 
	int j=0;
	for(; i<m;i++){
		while(j>0 && b[i]!=b[j]) j=p[j-1];
		if(b[i]==b[j]) j++;
		p[i]=j;
	}
	j=0;
	for(i=0;i<n;i++){
		while(b[j]!=a[i] && j>0) j=p[j-1];
		if(b[j]==a[i]) j++;
		if(j==m){
			sol++;
			rez[sol]=i-j+1;
		}
	}
	g<<sol<<endl;
	sol=min(sol, 1000);
	for(i=1;i<=sol;i++) g<<rez[i]<<' ';
	return 0;
}