Cod sursa(job #2393778)

Utilizator tziplea_stefanTiplea Stefan tziplea_stefan Data 1 aprilie 2019 00:40:53
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.14 kb
#include <fstream>
#include <vector>

using namespace std;

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

const int VAL=4000005;

int N, M, i, j, Z[VAL];
int L, R, poz, ANS;
string S, T;
vector <int> SOL;

int main()
{
    fin >> S >> T;
    N=S.size();
    M=T.size();
    S='*'+S+'*'+T+'*';
    for (i=2; i<=N+M+1; i++)
    {
        if (S[i]!=S[1])
        {
            Z[i]=0;
            continue;
        }
        if (i>R)
        {
            L=R=i;
            while (R<=N+M+1 && S[R]==S[R-L+1])
                R++;
            Z[i]=R-L;
            R--;
        }
        else
        {
            poz=i-L+1;
            if (Z[poz]<R-i+1)
                Z[i]=Z[poz];
            else
            {
                L=R=i;
                while (R<=N+M+1 && S[R]==S[R-L+1])
                    R++;
                Z[i]=R-L;
                R--;
            }
        }
        if (Z[i]==N)
        {
            ANS++;
            if (ANS<=1000)
                SOL.push_back(i-N-2);
        }
    }
    fout << ANS << '\n';
    for (i=0; i<SOL.size(); i++)
        fout << SOL[i] << " ";
    fin.close();
    fout.close();
    return 0;
}