Cod sursa(job #2181235)

Utilizator alex.info99polimernic alex.info99 Data 21 martie 2018 15:38:48
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.52 kb
#include<bits/stdc++.h>
using namespace std;
string a, b;
const int N=2000020;
int p[N];
int main(){
	ifstream f("strmatch.in");
	ofstream g("strmatch.out");
	f>>a>>b;
	int i=1, j=0;
	int n=a.size(), m=b.size();
	for(;i<n;i++){
		while(j>0 && a[i]!=a[j])j=p[j-1];
		if(a[i]==a[j])j++;
		p[i]=j;
	}
	j=0;
	int k=0;
	vector <int> s;
	for(i=0;i<m;i++){
		while(j>0 && b[i]!=a[j])j=p[j-1];
		if(b[i]==a[j])j++;
		if(j==n){
			k++;
			s.push_back(i-j+1);
		}
	}
	g<<k<<'\n';
	for(i=0;i<k;i++)g<<s[i]<<' ';
}