Cod sursa(job #1169764)

Utilizator costyrazvyTudor Costin Razvan costyrazvy Data 11 aprilie 2014 23:48:12
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.88 kb
#include <fstream>
#include <cstring>
#define mn(a,b) ((a<b) ? a : b)
using namespace std;
char S1[2000003],S1p[2000003];
char S2[2000003],S2p[2000003];
int N,M,i,k,pi[2000003],v[2000003],nr;
int main()
{
    ifstream f("strmatch.in");
    ofstream g("strmatch.out");
    f.get(S1p,2000002);f.get();
    f.get(S2p,2000002);f.get();
    strcat(S1,"%");
    strcat(S2,"%");
    strcat(S1,S1p);
    strcat(S2,S2p);
    N=strlen(S1);
    M=strlen(S2);
    N--;M--;
    for (i=2;i<=N;i++)
    {
        while ((k) && S1[i]!=S1[k+1]) k=pi[k];
        if (S1[i]==S1[k+1]) k++;
        pi[i]=k;
    }
    k=0;
    for (i=1;i<=M;i++)
    {
        while ((k) && S2[i]!=S1[k+1]) k=pi[k];
        if (S2[i]==S1[k+1]) k++;
        if (k==N) v[++nr]=i-N;
    }
    g<<nr<<'\n';
    for (i=1;i<=mn(nr,1000);i++) g<<v[i]<<" ";
    f.close();
    g.close();
    return 0;
}