Cod sursa(job #2417713)

Utilizator alexoloieriAlexandru Oloieri alexoloieri Data 30 aprilie 2019 21:27:46
Problema Potrivirea sirurilor Scor 38
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.26 kb
#include <bits/stdc++.h>
#define nmax 2000005
#define MOD 1000000007
#define lld long long
using namespace std;
FILE *fin=fopen("strmatch.in","r");
FILE *fout=fopen("strmatch.out","w");
char a[nmax], b[nmax];
int ln;
vector<int>ans;
lld expH, currH, pw[nmax];
const lld pww = 31;
int main()
{
    fscanf(fin,"%s\n",a);
    fscanf(fin,"%s\n",b);
    pw[0] = 1;
    ln = 1;
    for (int i=1;a[i];++i)
        pw[i] = (pw[i-1] * pww) % MOD, ++ln;
    if (!b[ln-1])
    {
        fprintf(fout,"0\n");
        return 0;
    }
    for (int i=ln-1;i>=0;--i)
        expH = (expH + pw[ln-i-1]*a[i]) % MOD;
    for (int i=ln-1;i>=0;--i)
        currH = (currH + pw[ln-i-1]*b[i]) % MOD;
    if (expH == currH)
        ans.push_back(1);
    for (int i=ln;b[i];++i)
    {
        currH = (currH - pw[ln-1]*b[i-ln]) % MOD;
        if (currH < 0) currH = MOD + currH;
        currH = (currH * pww + b[i]) % MOD;
        if (expH == currH)
        {
            ans.push_back(i-ln+1);
            if (ans.size() == 1000) break;
        }
    }
    fprintf(fout,"%d\n",ans.size());
    if (ans.size())
    {
        for (auto x:ans)
            fprintf(fout,"%d ", x);
        fprintf(fout,"\n");
    }
    fclose(fin);
    fclose(fout);
    return 0;
}