Cod sursa(job #2369529)

Utilizator HaesteinnSabau Florin Vlad Haesteinn Data 6 martie 2019 00:21:06
Problema Potrivirea sirurilor Scor 16
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.05 kb
#include <bits/stdc++.h>
#define NMAX 2000005
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
typedef long long ll;
const ll MOD=1000000007;
const ll P=997898399;

string a,b;
ll hashish;
ll p[NMAX],h[NMAX];

void precalculate()
{
    h[0]=b[0];
    for(int i=0;i<b.length();i++)
        h[i]=(h[i-1]*P+b[i])%MOD;
    p[0]=1;
    for(int i=1;i<b.length();i++)
        p[i]=(p[i-1]*P)%MOD;
    hashish=a[0];
    for(int i=1;i<a.length();i++)
        hashish=(hashish*P+a[i])%MOD;
}


int nr;

inline ll hashing(int st,int dr)
{
    if(st==0) return h[dr];
    return (h[dr]-(h[st-1]*p[dr-st+1])%MOD)%MOD;
}

int main()
{
    fin>>a>>b;
    vector<int> poz;
    int aL=a.length();
    int bL=b.length();
    precalculate();
//    fout<<hashish<<" "<<hashing(5,7);
    for(int i=0;i<=bL-aL;i++)
    {
        if(hashish==hashing(i,i+aL-1))
        {
            nr++;
            poz.push_back(i);
        }
    }
    fout<<nr<<'\n';
    for(auto x:poz)
        fout<<x<<' ';
    return 0;
}