Cod sursa(job #1895250)

Utilizator virtualityBbbbbbbbbbbbbbbbbb virtuality Data 27 februarie 2017 20:59:05
Problema Potrivirea sirurilor Scor 16
Compilator cpp Status done
Runda Arhiva educationala Marime 0.88 kb
#include<bits/stdc++.h>
#define N 2000020
using namespace std;
int  p[N], rs[N];
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;
	for (i = 2, p[1] = 0; i <= m; ++i)
    {
        while (q && b[q+1] != b[i])
            q = p[q];
        if (b[q+1] == b[i])
            ++q;
        p[i] = q;
    }
/*	while(i<m){
		if(b[len]==b[i]){
			len++;
			p[i]=len;
			i++;
		}else{
			if(len == 0){
				p[i]=0;
				i++;
			}else{
				len=p[len-1];
				
			}
		}
	}*/
	i=0;
	j=0;
	while(i<n){
		if(a[i]==b[j]){
			i++;
			j++;
		}
		if(j==m){
			rs[++k]=i-j;
			j=p[j-1];
		}
		else if(i<n && a[i]!=b[j]){
			if(j!=0){
				j=p[j-1];
			}else{
				i++;
			}
		}
	}
	g<<k<<endl;
	for(i=1;i<=k;i++) g<<rs[i]<<' ';
	return 0;
}