Cod sursa(job #3229034)

Utilizator ChopinFLazar Alexandru ChopinF Data 13 mai 2024 11:40:29
Problema Potrivirea sirurilor Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.1 kb
#include <bits/stdc++.h>

using namespace std;
#define d 256
const int q = 1e6 + 7;
std::ifstream fin("strmatch.in");
std::ofstream fout("strmatch.out");

std::string s1 , s2;
vector<int>ans;
int h , p , t;
int main()
{
    p = 0;
    t = 0;
    h = 1;

    fin >> s1 >> s2;
    for(int i = 0 ; i < s1.size() - 1 ; ++i)
        h = (h * d) % q;

    for(int i = 0 ; i < s1.size() ; ++i)
    {
            p = (d * p + s1[i]) % q;
            t = (d * t + s2[i]) % q;
    }

    for(int i = 0 ; i <= s2.size() - s1.size() ; ++i)
    {
       // fout << p << " " << t << "\n";
        if(p == t){
            bool ok = true;
            for(int j = 0 ; j < s1.size() && ok; ++j)
            {
                if(s1[j] != s2[i + j])ok = false;
            }
            if(ok == true)ans.push_back(i);
        }
        t = (d * (t - s2[i] * h) + s2[i + s1.size()]) % q;
     //   t = (d * (t - s2[i] * h) + s2[i + s1.size()]) % q;

        if(t < 0)t += q;
    }
    //fout << h << "\n";
    fout << ans.size() << "\n";
    for(int i = 0 ; i < std::min(1000 , (int)ans.size()) ; ++i)
    {
        fout << ans[i] << " ";
    }
}