Cod sursa(job #1150743)

Utilizator dutzulBodnariuc Dan Alexandru dutzul Data 23 martie 2014 14:47:39
Problema Potrivirea sirurilor Scor 28
Compilator cpp Status done
Runda Arhiva educationala Marime 0.83 kb
#include <iostream>
#include <fstream>

using namespace std;

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

#include <cstring>
#define LE 4000666
#define cout g

string str,str1;
int Z[LE],result;

int main()
{
    f>>str>>str1;
    int ni=str.length();
    str+=str1;
    int st=0,dr=0;
    int N=str.length();
    str+="  ";

    for(int i=1; i<N; ++i)
    {
        int P=i;
        if (dr>=i) P+=Z[i-st];
        while (str[P]==str[P-i])++P;
        Z[i]=P-i;
        if (P-1>dr) st=i,dr=P-1;
    }

    for(int i=ni; i<N-ni+1; ++i)
        if (Z[i]>=ni)
            ++result;

    cout<<result<<'\n';

    for(int nr=0,i=ni; i<N-ni+1; ++i)
        if (Z[i]>=ni)
            if (nr+1<=1000)
            {
                cout<<i-ni<<" ";
                ++nr;
            }
    return 0;
}