Cod sursa(job #932991)

Utilizator AtlasCalament Zidaru Atlas Data 29 martie 2013 14:42:41
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.5 kb
#include <fstream>
#include <cstring>
#include <vector>
using namespace std;

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

const int Nmax = 2000010;

char S1[Nmax],S2[Nmax],S[Nmax<<1];
int Left,Right,N1,N2,N;
int Z[Nmax];

vector<int> Sol;
int Co;

void Extend(int &left,int &right)
{
    int now = right - left + 1;
    if ( now > 0 )
        while ( S[now] == S[right] && right <= N )
            ++now , ++right;
}

int main()
{
    F.getline(S1,Nmax,'\n'), N1 = strlen( S1 );
    F.getline(S2,Nmax,'\n'), N2 = strlen( S2 );

    N = N1 + N2;
    for (int i=1;i<=N1;++i) S[i] = S1[i-1];
    for (int j=N1;j<N;++j) S[j+1] = S2[j-N1];
    S[N+1] = '#';

    Left = Right = 1 , Z[1] = N;
    for (int i=2;i<=N;++i)
    {
        if ( Left <= i && i <= Right )
        {
            if ( i+Z[i-Left+1]-1 < Right )
            {
                Z[i] = Z[i-Left+1];
            }
            else
            {
                Left = i;
                Extend(Left,Right);
                Z[i] = Right - Left, --Right;
            }
        }
        else
        {
            Left = Right = i;
            Extend(Left,Right);
            Z[i] = Right - Left, --Right;
        }

        if ( Z[i] >= N1 && i > N1 )
        {
            ++Co;
            if ( Sol.size() < 1000 )
                Sol.push_back( i-N1-1 );
        }
    }

    G<<Co<<'\n';
    for (vector<int>::iterator it=Sol.begin();it!=Sol.end();++it)
        G<<*it<<' ';
    G<<'\n';
}