Cod sursa(job #1449367)

Utilizator patrutoiuandreipatrutoiu andrei patrutoiuandrei Data 9 iunie 2015 12:54:48
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.97 kb
#include <fstream>
#include <string.h>

#define dim 2000001
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

int i,k,poz[1001],p[dim],n,m,nrpoz;
char s1[dim],s2[dim];
int main()
{
    fin>>(s1+1)>>(s2+1);
    n=strlen(s1+1);
    m=strlen(s2+1);
    for(i=2;i<=n;i++)
    {
        while(k>0 && s1[i] != s1[k+1])
        {
            k=p[k];
        }
        if(s1[i]==s1[k+1])
        {
            k++;
        }
        p[i]=k;
    }
    k=0;
    for(i=1;i<=m;i++)
    {
        while(k>0 && s2[i] != s1[k+1])
        {
            k=p[k];
        }
        if(s2[i] == s1[k+1])
        {
            k++;
        }
        if(k == n)
        {
            if(nrpoz<1000)
                poz[++nrpoz]=i-n;
            else
                nrpoz++;
             k=p[k];
        }
    }
    fout<<nrpoz<<'\n';
    for(i=1;i<=nrpoz&& i<=1000;i++)
    {
        fout<<poz[i]<<' ';
    }
    return 0;
}