Cod sursa(job #1402057)

Utilizator EpictetStamatin Cristian Epictet Data 26 martie 2015 11:57:31
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.87 kb
#include <fstream>
#include <string>
#include <vector>
#define MOD 666013
#define P 73
using namespace std;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
string A, B;
vector < int > V;
int h, h1, sol, PP = 1;

int main()
{
    fin >> A >> B;
    for (int i = 0; i < A.size(); i++) {
        h = (h * P + A[i]) % MOD;
        if (i != 0) PP = (PP * P) % MOD;
    }

    for (int i = 0; i < A.size(); i++) {
        h1 = (h1 * P + B[i]) % MOD;
    }

    if (h == h1) sol++, V.push_back(0);
    for (int i = A.size(); i < B.size(); i++)
    {
        h1 = (((h1 - (PP * B[i - A.size()])) % MOD + MOD) * P + B[i]) % MOD;
        if (h == h1) {
            sol++;
            V.push_back(i - A.size() + 1);
        }
    }

    fout << sol << '\n';
    for (auto it : V) {
        fout << it << ' ';
    }

    fout.close();
    return 0;
}