Cod sursa(job #1896017)

Utilizator virtualityBbbbbbbbbbbbbbbbbb virtuality Data 28 februarie 2017 13:20:11
Problema Potrivirea sirurilor Scor 32
Compilator cpp Status done
Runda Arhiva educationala Marime 0.58 kb
#include<bits/stdc++.h>
#define N 2000020
using namespace std;
int  p[N], rs[N];
vector <int> s;
int main(){
	string a, b;
	int n, m, k=0;
	ifstream f("strmatch.in");
	ofstream g("strmatch.out");
	f>>b>>a;
	n=a.length();
	m=b.length();
	p[0]=0;
	int len=0, i=1, j, q=0;
	  j=0;
	for(i=1;i<m;i++) {
		while(b[i]!=b[j] && j>0) j=p[j-1];
		if(b[i]==b[j])j++;
		p[i]=j;
	}
	for(i=0;i<n;i++){
		while(j>0 && a[i]!=b[j]){
				j=p[j-1];
		}
		if(a[i]==b[j])j++;
		if(j==m) s.push_back(i-m+1);
		
	}

	g<<s.size()<<endl;
	for(i=0;i<s.size();i++) g<<s[i]<<' ';
	return 0;
}