Cod sursa(job #1399917)

Utilizator Andreiii500Andrei Puiu Andreiii500 Data 24 martie 2015 23:43:42
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.43 kb
#include<string.h>
#include<fstream>
//#include<iomanip>
using namespace std;

// 2000005
#define dim 2000005

//ifstream in("date.in");
//ofstream out("date.out");

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

char cuv[dim];
char sir[dim];
int lung[dim];
int poz[dim];

int n,m;

int main()
{
    int i,j,k,cnt=0;

    in>>cuv;
    m=strlen(cuv);
    in>>sir;
    n=strlen(sir);

    lung[0]=0;
    for(i=1;i<m;++i)
    {
        k=lung[i-1];
        while(k>0)
        {
            if(cuv[k]==cuv[i]) break;
            k=lung[k-1];
        }
        if(cuv[k]==cuv[i]) lung[i]=k+1;
        else lung[i]=0;
    }

    i=0;
    j=0;
    while(i<n)
    {
        if(cuv[j]==sir[i])
        {
            ++i;
            ++j;

            if(j==m)
            {
                poz[cnt++]=i-j;
                //out<<(i-j)<<" ";
                //out<<"Gasit pe "<<(i-j)<<"\n";
                j=lung[j-1];
            }
        }
        else
        {
            if(j==0) ++i;
            else j=lung[j-1];
        }
    }

    out<<cnt<<"\n";
    for(i=0;i<cnt;++i) out<<poz[i]<<" ";

    /*
    for(i=0;i<m;++i) out<<setw(3)<<cuv[i]; out<<"\n";
    for(i=0;i<m;++i) out<<setw(3)<<lung[i]; out<<"\n";
    out<<"\n";

    for(i=0;i<n;++i) out<<setw(3)<<sir[i]; out<<"\n";
    for(i=0;i<n;++i) out<<setw(3)<<i; out<<"\n";
    out<<"\n";
    */


    return 0;
}