Cod sursa(job #2793307)

Utilizator Ana100Ana-Maria Tomoiala Ana100 Data 3 noiembrie 2021 14:14:23
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.45 kb
#include <fstream>

using namespace std;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
const int mod=666013;
const int base=13;
int poz[1005];
int lgput(int baza, int exp)
{
   if(exp==0)
        return 1;
   int aux=lgput(baza,exp/2);
   if(exp%2==0)
    return (aux*aux)%mod;
   else
    return ((aux*aux)%mod)*baza%mod;
}
int hashing(string str, int len)
{
    int hash1,i;
    i=0;
    while(i<len)
    {
        hash1=(hash1*base+str[i])%mod;
        i++;
    }
    return hash1;

}
int addtohash(int hash1,char c)
{
    return (hash1*base+c)%mod;
}
int removefromhash(int hash1, char c, int power)
{
    hash1-=c*power%mod;
    if(hash1<0)
        hash1+=base;
    return hash1;
}
int main()
{
    string pattern, text;
    int patternlengh,cnt=0,k=0;
    cin>>pattern;
    patternlengh=pattern.size();
    int patternhash=hashing(pattern,patternlengh);
    int power=lgput(base,patternlengh-1);
    cin>>text;
    int texthash=hashing(text,patternlengh-1);
    for(int i=patternlengh-1;i<text.size();i++)
    {
        texthash=addtohash(texthash,text[i]);
        if(texthash==patternhash)
            {
                cnt++;
                if(i-patternlengh+1<=1000)
                   poz[++k]=i-patternlengh+1;
            }
        texthash=removefromhash(texthash,text[i-patternlengh+1],power);
    }
    cout<<cnt<<endl;
    for(int i=1;i<=k;i++)
        cout<<poz[i]<<" ";
    return 0;
}