Cod sursa(job #1155446)

Utilizator Dragan_ValentinDragan Valentin Dragan_Valentin Data 26 martie 2014 22:02:58
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 1.29 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;
    for (int i=1; i<strlen(p); i++)
        if ( p[i]==p[v[i-1]]) v[i]=v[i-1]+1;
        else if (v[i-1]!=0 && p[i]==p[0]) v[i]=1;
        else v[i]=0;
}

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

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

    f.getline(p,sizeof(p));
    ChupaChups_p();
    f.getline(s,sizeof(s));
    SearchPinS();

    g<<nr<<'\n';
    for (int i=0; i<nr; i++)
        g<<aparitii[i]<<' ';

    return 0;
}