Cod sursa(job #1520327)

Utilizator dragos000Cojanu Dragos dragos000 Data 8 noiembrie 2015 16:47:11
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 0.94 kb
#include <iostream>
#include <cstring>
#include <fstream>

using namespace std;

char a[2000005],b[2000005];
int n,m,pi[12000005],rez[1024],N;
void citire()
{
    ifstream f("strmatch.in");
    f.getline(a,2000005);f.getline(b,2000005);
    f.close();
    n=strlen(a);
    m=strlen(b);
}

void prefix()
{
    int q=0,i;

    for (i=2;i<=m;i++)
    {
        while (q>0&&b[q]!= b[i])
            q=pi[q-1];
        if (b[q]==b[i])
            q++;
        pi[i] = q;
    }
}

void fct()
{

    int q=0;

    for(int i=1;i<=n;i++)
        {
        while(q>0 && b[q]!=a[i])
        q=pi[q-1];

        if(b[q]==a[i]) q++;
        if(q==m)
        {
        q=pi[q];
        N++;
        rez[N]=i-m;
        }
        }

}



int main()
{
    citire();
    prefix();
    fct();

    ofstream g("strmatch.out");
    g<<N<<endl;
    for(int i=1;i<=N;i++)
        g<<rez[i]<<" ";

    return 0;
}