Cod sursa(job #2393782)

Utilizator tziplea_stefanTiplea Stefan tziplea_stefan Data 1 aprilie 2019 00:48:07
Problema Potrivirea sirurilor Scor 38
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.1 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)
        {
            Z[i]=1;
            while (S[1+Z[i]]==S[i+Z[i]])
                Z[i]++;
            L=i;
            R=i+Z[i]-1;
        }
        else
        {
            poz=i-L+1;
            Z[i]=min(Z[poz], R-i+1);
            while (S[1+Z[i]]==S[i+Z[i]])
                Z[i]++;
            if (i+Z[i]-1>R)
            {
                L=i;
                R=i+Z[i]-1;
            }
        }
        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;
}