Cod sursa(job #2211188)

Utilizator AlexandruabcdeDobleaga Alexandru Alexandruabcde Data 9 iunie 2018 15:26:43
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.56 kb
#include <fstream>
#include <vector>
#include <cstring>
#define Mod2 666013
#define Mod1 10003
#define in1 127
#define in2 131

using namespace std;

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

vector <int> s;

int n, m, x1, x2, y1, y2, p1, p2;

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';
    }
    else
    {
        ///127 131
        for (int i = 0; i < n; i++)
        {
            x1 = ((x1 * in1) % Mod1 + (A[i] - '0')) % Mod1;
            x2 = ((x2 * in2) % Mod2 + (A[i] - '0')) % Mod2;
            y1 = ((y1 * in1) % Mod1 + (B[i] - '0')) % Mod1;
            y2 = ((y2 * in2) % Mod2 + (B[i] - '0')) % Mod2;
        }

        p1 = p2 = 1;
        for (int i = 1; i < n; i++)
        {
            p1 = (p1 * in1) % Mod1;
            p2 = (p2 * in2) % Mod2;
        }

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

        for (int i = n; i < m; i++)
        {
            y1 = ((y1 - (p1 * (B[i - n] - '0')) % Mod1 + Mod1) * in1 + (B[i] - '0')) % Mod1;
            y2 = ((y2 - (p2 * (B[i - n] - '0')) % Mod2 + Mod2) * in2 + (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;
}