Cod sursa(job #2196524)

Utilizator alexsandulescuSandulescu Alexandru alexsandulescu Data 19 aprilie 2018 17:32:38
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 1.14 kb
#include <bits/stdc++.h>
#define M1 666013
#define M2 10013
#define B1 127
#define B2 131

using namespace std;

ifstream f("strmatch.in");
ofstream g("strmatch.out");

int ss1, ss2, s1, s2;
vector<int> s;
char sstr[2000003], str[2000003];
int main()
{
    f >> sstr >> str;
    int N = strlen(sstr), M = strlen(str);
    for(int i = 0; i < N; i++)
        ss1 = (ss1 * B1 % M1 + (sstr[i] - '0')) % M1,
        ss2 = (ss2 * B2 % M2 + (sstr[i] - '0')) % M2,
        s1 =  (s1 * B1 % M1 + (str[i] - '0')) % M1,
        s2 =  (s2 * B2 % M2 + (str[i] - '0')) % M2;
    int p1 = 1, p2 = 1;
    for(int i = 1; i < N; i++)
        p1 = p1 * B1, p2 = p2 * B2;

    if(ss1 == s1 && ss2 == s2)
        s.push_back(0);
    for(int i = N; i < M; i++) {
        s1 = (((s1 - ((str[i - N] - '0') * p1)) % M1 + M1) * B1 + (str[i] - '0')) % M1;
        s2 = (((s2 - ((str[i - N] - '0') * p2)) % M2 + M2) * B2 + (str[i] - '0')) % M2;
        if(ss1 == s1 && ss2 == s2)
            s.push_back(i - N + 1);
    }
    g << s.size() << "\n";
    for(int i = 0; i < s.size() && i < 1000; i++)
        g << s[i] << " ";
    g << "\n";
    return 0;
}