Cod sursa(job #1156660)

Utilizator Dragan_ValentinDragan Valentin Dragan_Valentin Data 27 martie 2014 20:42:55
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1 kb
#include <iostream>
#include <fstream>
#include <cstring>

using namespace std;

char p[2000000];
char s[2000000];
int v[2000000];
int aparitii[1000000];
int nr=0;

void ChupaChups_p()
{
    v[0]=0;
    int j=0;
    for (int i=1; i<strlen(p); i++) {
        while (j>0 && p[i]!=p[j]) j=v[j-1];
        if (p[i]==p[j]) ++j;
        v[i]=j;
    }
}

void SearchPinS()
{
    int i,j=0;
    for (i=0; i<strlen(s); i++) {
        while (j>0 && s[i]!=p[j]) j=v[j-1];
        if (s[i]==p[j]) {
            //cout<<" Match ! ";
            ++j;
            if (j==strlen(p)) {
                //cout<<" Found... ";
                aparitii[nr++]=i-j+1;
                j=v[j-1];
            }
        }
    //cout<<i<<' '<<j<<' '<<'\n';
    }
}

int main()
{
    ifstream f("strmatch.in");
    ofstream g("strmatch.out");

    f>>p;
    ChupaChups_p();
    f>>s;
    SearchPinS();
    g<<nr<<'\n';
    for (int i=0; i<nr; i++)
        g<<aparitii[i]<<' ';

    return 0;
}