Cod sursa(job #2632467)

Utilizator AlexandruabcdeDobleaga Alexandru Alexandruabcde Data 3 iulie 2020 13:18:28
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.47 kb
#include <fstream>
#include <vector>
#include <cstring>
#define Mod2 666013
#define Mod1 10003
#define put1 127
#define put2 131

using namespace std;

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

vector <int> s;

int N, M, x1, x2, y1, y2, power1, power2;

char A[2000002];
char B[2000002];

int main()
{
    f.getline(A,2000002);
    f.getline(B,2000002);

    N = strlen(A);
    M = strlen(B);

    if (N > M)
    {
        g << 0 << '\n';
        return 0;
    }

    for (int i = 0; i < N; ++ i )
    {
        x1 = ((x1 * put1) % Mod1 + (A[ i ] - '0')) % Mod1;
        x2 = ((x2 * put2) % Mod2 + (A[ i ] - '0')) % Mod2;
        y1 = ((y1 * put1) % Mod1 + (B[ i ] - '0')) % Mod1;
        y2 = ((y2 * put2) % Mod2 + (B[ i ] - '0')) % Mod2;
    }

    power1 = power2 = 1;
    for (int i = 1; i < N; ++ i )
    {
        power1 = (power1 * put1) % Mod1;
        power2 = (power2 * put2) % Mod2;
    }

    if (x1 == y1 && x2 == y2)
    {
        s.push_back(0);
    }

    for (int i = N; i < M; ++ i )
    {
        y1 = ((y1 - (power1 * (B[i - N] - '0')) % Mod1 + Mod1) * put1 + (B[i] - '0')) % Mod1;
        y2 = ((y2 - (power2 * (B[i - N] - '0')) % Mod2 + Mod2) * put2 + (B[i] - '0')) % Mod2;

        if (y1 == x1 && y2 == x2)
        {
            s.push_back(i - N + 1);
        }
    }

    g << s.size() << '\n';

    for (int i = 0; i < 1000 && i < s.size(); ++ i )
        g << s[i] << " ";

    return 0;
}