Cod sursa(job #794405)

Utilizator gramatovici_paulGramatovici Paul gramatovici_paul Data 6 octombrie 2012 11:55:53
Problema Potrivirea sirurilor Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.21 kb
#include <iostream>
#include <fstream>

using namespace std;

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

char a[2222222],b[2222222];
int t[2222222],rez[2222222];
int k,pos,i,l,nr;

int main()
{
    in.getline(a,2222222);
    in.getline(b,2222222);
    t[0]=-1;
    t[1]=0;
    k=0;
    pos=2;
    l=2;
    while(a[pos])
    {
        if(a[pos-1]==a[k])
        {
            t[pos]=++k;
            pos++;
        }
        else
        {
            if(k!=0)
                k=t[k];
            else
                t[pos++]=0;
        }
        ++l;
    }
    --l;
   // for(i=0;a[i];++i)
     //   out<<i<<" "<<t[i]<<"\n";
    k=0;
    pos=0;
    while(b[pos])
    {
        if(b[pos]==a[k])
        {
            if(l-1==k)
            {
                rez[++nr]=pos-k;
                k=t[k];
            }
            else
            {
                k++;
                pos++;
            }

        }
        else
        {
            if(k==0)
            {
                pos++;
                continue;
            }
            k=t[k];
        }
    }
    out<<nr<<"\n";
    for(i=1;i<=nr;++i)
        out<<rez[i]<<" ";
    return 0;
}