Cod sursa(job #1299513)

Utilizator ArchazeyBaltatu Andrei-Mircea Archazey Data 23 decembrie 2014 18:18:13
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.93 kb
//K-algorithm
#include<bits/stdc++.h>
using namespace std;

ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

const int NMAX=2000005;
const int XMAX=4000005;

char a[NMAX],b[NMAX],c[XMAX];
int sol[NMAX],pi[XMAX];

int main()
{
    int i,lena,lenb,lenc,dr;
    fin>>(a+1);
    lena=strlen(a+1);
    fin>>(b+1);
    lenb=strlen(b+1);
    for (i=1;i<=lena;i++) c[i]=a[i];
    c[lena+1]='#';
    for (i=1;i<=lenb;i++) c[lena+1+i]=b[i];
    lenc=lena+lenb+1;
    pi[1]=0;
    for (i=2;i<=lenc;i++)
        {
            dr=pi[i-1];
            while (dr && c[dr+1]!=c[i]) dr=pi[dr];
            if (c[dr+1]==c[i]) dr++;
            pi[i]=dr;
            if (pi[i]==lena) sol[++sol[0]]=i-lena+1;
        }
    fout<<sol[0]<<"\n";
    for (i=1;i<=min(1000,sol[0]);i++)
        {
            sol[i]-=lena;
            sol[i]-=2;
            fout<<sol[i]<<" ";
        }
    fout<<"\n";
    return 0;
}