Cod sursa(job #2361415)

Utilizator tanasaradutanasaradu tanasaradu Data 2 martie 2019 15:29:33
Problema Potrivirea sirurilor Scor 32
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.68 kb
#include <bits/stdc++.h>

using namespace std;

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

const int P = 26;
const int Mod = 123457;
const int Mod1 = 1000003;
const int Nmax = 2e6 + 5;

char a[Nmax], b[Nmax];

int prod1, prod2, ans[1005], d, n, m;

int main()
{
    int x, y, xx, yy;
    fin >> (a + 1) >> (b + 1);
    n = strlen(a + 1);
    m = strlen(b + 1);
    for(int i = 1 ; i <= n ; i++)
        if('A' <= a[i] && a[i] <= 'Z')
            a[i] = a[i] - 'A' + 'a';
    for(int i = 1 ; i <= m ; i++)
        if('A' <= b[i] && b[i] <= 'Z')
            b[i] = b[i] - 'A' + 'a';
    if(n > m)
    {
        fout << "0\n";
        return 0;
    }
    prod1 = prod2 = 1;
    x = y = xx = yy = 0;
    for(int i = 1 ; i <= n ; i++)
    {
        x = (x * P + (a[i] - 'a')) % Mod;
        y = (y * P + (a[i] - 'a')) % Mod1;
        xx = (xx * P + (b[i] - 'a')) % Mod;
        yy = (yy * P + (b[i] - 'a')) % Mod1;
        if(i == 1)
            continue;
        prod1 = (prod1 * P) % Mod;
        prod2 = (prod2 * P) % Mod1;
    }

    if(x == xx && y == yy)
        ans[++d] = 0;
    for(int i = n + 1 ; i <= m && d < 1000 ; i++)
    {
        xx = ((xx - ((b[i - n] - 'a') * prod1) % Mod + Mod) % Mod * P + (b[i] - 'a')) % Mod;
        yy = ((yy - ((b[i - n] - 'a') * prod2) % Mod1 + Mod1) % Mod1 * P + (b[i] - 'a')) % Mod1;
        ///cout << x << " " << y << " " << xx << " " << yy << " " << i - n << "\n";
        if(x == xx && y == yy)
            ans[++d] = i - n;
    }
    fout << d << "\n";
    for(int i = 1 ; i <= d ; i++)
        fout << ans[i] << " ";
    fout << "\n";
    fin.close();
    fout.close();
    return 0;
}