Cod sursa(job #1983403)

Utilizator tziplea_stefanTiplea Stefan tziplea_stefan Data 21 mai 2017 21:17:56
Problema Potrivirea sirurilor Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.18 kb
#include <fstream>
#include <vector>
#define MOD 666013

using namespace std;

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

int LP, LT, i, j, nr;
int NRP, NRT, Prod;
vector <int> SOL;
vector <int> :: iterator it;
string P, T;

bool Verify(int K)
{
    int i;
    for (i=0; i<LP; i++)
      if (P[i]!=T[i+K])
        return false;
    return true;
}

int main()
{
    fin >> P >> T;
    LP=P.size();
    LT=T.size();
    Prod=1;
    for (i=LP-1; i>=0; i--)
    {
        NRP+=Prod*(P[i]);
        NRP%=MOD;
        NRT+=Prod*(T[i]);
        NRT%=MOD;
        if (i!=0)
        {
            Prod*=199;
            Prod%=MOD;
        }
    }
    if (NRT==NRP && Verify(0)==true)
      SOL.push_back(0);
    for (i=LP; i<LT; i++)
    {
        nr=Prod*(T[i-LP]);
        nr%=MOD;
        NRT-=nr;
        if (NRT<0)
          NRT=MOD+(NRT % MOD);
        NRT*=199;
        NRT%=MOD;
        NRT+=T[i];
        if (NRT>=MOD)
          NRT-=MOD;
        if (NRT==NRP && Verify(i-LP+1)==true)
          SOL.push_back(i-LP+1);
    }
    fout << SOL.size() << '\n';
    int K=SOL.size();
    for (i=0; i<min(K, 1000); i++)
      fout << SOL[i] << " ";
    fin.close();
    fout.close();
    return 0;
}