Cod sursa(job #932988)

Utilizator AtlasCalament Zidaru Atlas Data 29 martie 2013 14:41:25
Problema Potrivirea sirurilor Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.48 kb
#include <fstream>
#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;
    while ( S[now] == S[right] && right <= N ) ++now , ++right;
}

int main()
{
    F.getline(S1,Nmax,'\n'); while ( S1[N1] != 0 ) ++N1; --N1;
    F.getline(S2,Nmax,'\n'); while ( S2[N2] != 0 ) ++N2; --N2;

    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';
}