Cod sursa(job #2196541)

Utilizator alexsandulescuSandulescu Alexandru alexsandulescu Data 19 aprilie 2018 18:11:55
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.17 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) % M1, p2 = (p2 * B2) % M2;

    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;
}