Cod sursa(job #2938613)

Utilizator patrickunudoiBeres Patrick Stefan patrickunudoi Data 12 noiembrie 2022 13:34:23
Problema Potrivirea sirurilor Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.71 kb
#include <iostream>
#include <string>
#include <vector>
using namespace std;
string s1,s2;
unsigned long long h1,h2,p_n=1;
vector <int> prez;
long long p=31;
int main()
{
    cin>>s1>>s2;
    if(s1.size() > s2.size())
        swap(s1,s2);
    for(int i=0; i<s1.size();i++)
    {
        h1 = h1 *p + s1[i];
        h2 = h2 *p + s2[i];
        p_n=p_n*p;
    }
    if(h1 == h2)
        prez.push_back(0);
    for(int i = s1.size();i<s2.size();i++)
    {
        h2=h2 * p +s2[i]-p_n*s2[i-s1.size()];
        if(h1==h2)
           prez.push_back(i-s1.size()+1);
    }
    cout<<prez.size()<<endl;;
    for(int i=0;i<=min(1000,(int)prez.size());i++)
        cout<<prez[i]<<' ';
    return 0;
}