Cod sursa(job #3258189)

Utilizator MilitaruMihaiMihaiMIlitaru MilitaruMihai Data 21 noiembrie 2024 15:39:45
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.91 kb
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int MOD1=1e9+7,MOD2=1e9+13;
int p1=31,p2=37;

vector <int> ans;
string s1,s2;
int n,v;
int main()
{
    fin>>s1;
    int has1=0,pow1=1;
    for (int i=0;i<s1.size();i++)
    {
        has1=has1*p1+s1[i];
        has1%=MOD1;
        if(i) pow1*=p1%MOD1;
    }
    //cout<<pow1<<' '<<has1<<'\n';
    fin>>s2;
    int has2=0;
    for (int i=0;i<s1.size();i++){
        has2=has2*p1+s2[i];
        has2%=MOD1;
    }
    if (has1==has2) ans.push_back(0);
    for (int i=s1.size();i<s2.size();i++){
        has2=(p1*((has2+MOD1-(s2[i-s1.size()]*pow1))%MOD1)+s2[i])%MOD1;
        //cout<<has2<<" ";
        if (has2==has1) ans.push_back(i-s1.size()+1);
    }
    fout<<ans.size()<<'\n';
    for (int i=0;i<ans.size();i++)
        fout<<ans[i]<<' ';
    return 0;
}