Cod sursa(job #1800208)

Utilizator vladm98Munteanu Vlad vladm98 Data 7 noiembrie 2016 15:50:49
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 1.05 kb
#include <bits/stdc++.h>

using namespace std;
const int m1 = 100000007;
 int h[2000001], b[2000001];
long long baza = 17;
long long cheie;
long long var;
int i, n, m, contor, raspuns[2000001];
char c[2000000], s[2000000];
int main()
{
    ifstream fin ("strmatch.in");
    ofstream fout ("strmatch.out");
    fin.getline(c, 2000000);
    fin.getline(s, 2000000);
    for (i = strlen(c)-1; i>=0; --i)
        cheie = (cheie*baza + c[i])%m1;
    for (i = strlen(s)-1; i>=0; --i)
        {
            var = h[i+1]*baza +s[i];
            h[i] = var%m1;
        }
    n = strlen(s);
    m = strlen(c);
    b[0] = 1;
    for (i = 1; i<=n; ++i)
    {
        var = b[i-1]*baza;
        b[i] = (var)%m1;
    }
    for (i = m-1; i < n; ++i)
    {
        var = h[i+1]*b[m]%m1;
        var = (h[i-m+1] + m1 - var)%m1;
        if (cheie == var)
        {
            raspuns[contor] = i-m+1;
            ++contor;
        }
    }
    fout << contor << '\n';
    for (i=0; i<contor; ++i)
        fout << raspuns[i] << " ";
    return 0;
}