Cod sursa(job #1918558)

Utilizator adiXMGemene Adrian adiXM Data 9 martie 2017 15:57:56
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.02 kb
#include <bits/stdc++.h>

using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
const int nMax = 2000003;
const unsigned int Base = 97;
char a[nMax], b[nMax];
unsigned int Put[nMax], bhasuit[nMax];
inline unsigned int Decod(const int st,const int dr) {
    return bhasuit[dr] - bhasuit[st - 1] * Put[dr - st + 1];
}
vector <int> ans;
int main()
{
    unsigned int hs = 0;
    f >> (a + 1);
    f >> (b + 1);
    int n = strlen(a + 1);
    int m = strlen(b + 1);
    int cnt = 0;
    for(int i = 1; i <= n; i++) {
        hs = hs * Base + a[i];
    }
    Put[0] = 1;
    for(int i = 1; i <= m; i++) {
        bhasuit[i] = bhasuit[i - 1] * Base + b[i];
        Put[i] = Put[i - 1] * Base;
    }
    for(int i = n; i <= m; i++) {
        if(Decod(i - n + 1, i) == hs) {
            cnt++;
            if(cnt <= 1000) {
                ans.push_back(i - n);
            }
        }
    }
    g << cnt << "\n";
    for(const auto &i : ans) {
        g << i << " ";
    }
    return 0;
}