Cod sursa(job #2288891)

Utilizator alexandruilieAlex Ilie alexandruilie Data 24 noiembrie 2018 08:54:38
Problema Potrivirea sirurilor Scor 78
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.73 kb
#include <fstream>
#include <string.h>

using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
char s1[2000005],s2[2000005];
int k,n,m,sol[1005],p[2000005],i,nr;
int main()
{
    f.getline(s1+1,2000005);
    f.getline(s2+1,2000005);
    k=0;
    n=strlen(s1+1);
    m=strlen(s2+1);
    for(i=2;i<=n;i++)
    {
        for(;k!=0&&s1[k+1]!=s1[i];) k=p[k];
        if(s1[k+1]==s1[i]) k++;
        p[i]=k;
    }
    k=0;
    for(i=2;i<=m;i++)
    {
        for(;k!=0&&s1[k+1]!=s2[i];) k=p[k];
        if(s1[k+1]==s2[i]) k++;
        if(k==n) {
            nr++;
            if(nr<=1000) sol[nr]=i-n;
        }
    }
    g<<nr<<'\n';
    for(i=1;i<=min(nr,1000);i++) g<<sol[i]<<' ';
    return 0;
}