Cod sursa(job #2853795)

Utilizator elenacurecheriuElena Curecheriu elenacurecheriu Data 20 februarie 2022 17:11:12
Problema Potrivirea sirurilor Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.4 kb
#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>
using namespace std;

ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");

const int N = 4e6, d = 62, q = 666013;
string a, b, s;
long long a_len, b_len, s_len;
long long k, cnt;
vector <int> ans;
int main()
{
    fin>>a>>b;
    s='$'+a+'$'+b;
    a_len=a.size();
    b_len=b.size();
    s_len=s.size();
    if(a_len>b_len)
    {
        fout<<0;
        return 0;
    }
    int hash_a=0, hash_b=0;
    int h=1;
    for(int i=0; i<a_len-1; i++)
        h=(h*d)%q;
    for(int i=0; i<a_len; i++)
    {
        hash_a = (d * hash_a + a[i]) % q;
        hash_b = (d * hash_b + b[i]) % q;
    }
    int i, j;
    for(i=0; i<b_len-a_len; i++)
    {
        if(hash_a==hash_b)
        {
            bool ok=1;
            for(j=0; j<a_len; j++)
            {
                if(a[j] != b[i+j])
                {
                    ok=0;
                    break;
                }
                if(ok)
                    continue;
            }
            if(j==a_len)
                ans.push_back(i);
        }
        if(i<b_len-a_len)
        {
            hash_b=(d*(hash_b-b[i]*h)+ b[i+a_len])%q;
            if(hash_b<0)
                hash_b+=q;
        }
    }
    fout<<ans.size()<<'\n';
    for(int i=0; i<ans.size(); i++)
        fout<<ans[i]<<" ";
    return 0;
}