Cod sursa(job #1456956)

Utilizator greenadexIulia Harasim greenadex Data 2 iulie 2015 14:25:43
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.44 kb
#include <bits/stdc++.h>

using namespace std;

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

string s, r;
const int p1 = 100003, p2 = 666013, b1 = 157, b2 = 233;
int vaca1 = 1, vaca2 = 1, look1, look2, cod1, cod2, cnt;
vector <int> sol;


int main() {
    fin >> s >> r;
    int l1 = s.size(), l2 = r.size();

    for (int i = 1; i <= l1; i++) {
        look1 = (look1 + 1LL * vaca1 * s[l1 - i]) % p1;
        look2 = (look2 + 1LL * vaca2 * s[l1 - i]) % p2;
        if(i < l1) {
            vaca1 = (1LL * vaca1 * b1) % p1;
            vaca2 = (1LL * vaca2 * b2) % p2;
        }
    }

    for (int i = 0; i < l2; i++)
        if (i < l1) {
            cod1 = ((1LL * cod1 * b1) + r[i]) % p1;
            cod2 = ((1LL * cod2 * b2) + r[i]) % p2;
        } else {
            if (cod1 == look1 && cod2 == look2) {
                cnt++;
                if(sol.size() < 1000)
                    sol.push_back(i - l1);
            }
            cod1 = (cod1 + p1 - (1LL * vaca1 * r[i - l1]) % p1) % p1;
            cod1 = (1LL * cod1 * b1 + r[i]) % p1;
            cod2 = (cod2 + p2 - (1LL * vaca2 * r[i - l1]) % p2) % p2;
            cod2 = (1LL * cod2 * b2 + r[i]) % p2;
        }

    if(cod1 == look1 && cod2 == look2) {
        cnt++;
        if (sol.size() < 1000)
            sol.push_back(l2 - l1);
    }
    fout << cnt << '\n';
    for (auto it : sol)
        fout << it << ' ';

    return 0;
}