Cod sursa(job #2600460)

Utilizator betybety bety bety Data 12 aprilie 2020 17:19:39
Problema Potrivirea sirurilor Scor 32
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.91 kb
#include <fstream>
#include <vector>
using namespace std;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
vector<int> sol;
const int A=29;
const int B=666013;
int main()
{
    int rasp=0;
    string a,b;
    cin>>a>>b;
    if(a.size()>b.size())
    {
        cout<<0<<'\n';
        return 0;
    }
    int n=a.size(),ka=0,kb=0,power=1;
    for(int i=0;i<n;++i)
    {
        ka=(ka*A+a[i]-'A')%B;
        power=(power*A)%B;
    }
    for(int i=0;i<n;++i)
        kb=(kb*A+b[i]-'A')%B;
    if(ka==kb) ++rasp,sol.push_back(0);
    for(int i=1;i<=b.size()-n;++i)
    {
        kb=(kb*A+b[i+n-1]-'A')%B;
        kb=(kb-(power*(b[i-1]-'A'))%B+B)%B;
        if(ka==kb)
        {
            ++rasp;
            if(sol.size()<1000)
                sol.push_back(i);
        }
    }
    cout<<rasp<<'\n';
    for(int i=0;i<sol.size();++i)
        cout<<sol[i]<<' ';
    return 0;
}