Cod sursa(job #920588)

Utilizator Impaler_009Mihai Nitu Impaler_009 Data 20 martie 2013 15:49:58
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.66 kb
#include <fstream>
#include <string.h>
#define N 2000010
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

char s[N],big[N];
int p[N],k,sl,bigl,i,sol[N],nr,j;

int main()
{
    fin>>s+1;
    fin>>big+1;
    sl=strlen(s+1);
    bigl=strlen(big+1);
    p[1]=0; k=0;
    for (i=2;i<=sl;i++)
    {
    	while (k>0&&s[i]!=s[k+1]) k=p[k];
    	if (s[i]==s[k+1]) k++;
    	p[i]=k;
    }
    k=0; j=0;
    for (i=1;i<=bigl;i++)
    {
    	while (k>0&&s[k+1]!=big[i]) k=p[k];
    	if (s[k+1]==big[i]) {k++; if (k==sl) {nr++; sol[++j]=i-k;}}
    }
    fout<<nr<<"\n";
    for (i=1;i<=nr&&i<=1000;i++) fout<<sol[i]<<" ";
}