Cod sursa(job #2053551)

Utilizator tziplea_stefanTiplea Stefan tziplea_stefan Data 31 octombrie 2017 21:08:51
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.13 kb
#include <fstream>
#include <vector>
#define VAL 2000005

using namespace std;

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

int N, M, i, j, K;
int Z[VAL], L, R;
string P, T;
vector <int> SOL;

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