Cod sursa(job #2861475)

Utilizator anghelmrsmanghel eduard anghelmrsm Data 4 martie 2022 00:40:23
Problema Potrivirea sirurilor Scor 34
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.99 kb
#include <fstream>
#include <string>
#include <vector>

using namespace std;

ifstream cin("strmatch.in");
ofstream cout("strmatch.out");

string s,x;
vector <int> v;
#define mod 1009
unsigned long long int nr,nr1;
bool ok=true;
int main()
{
    cin>>x;
    cin>>s;
    int n=s.size(),m=x.size();
    for (int i=0; i<m; i++)
    {
        nr=(nr+s[i])%mod;
        nr1=(nr1+x[i])%mod;
        if (s[i]!=x[i])
            ok=false;
    }
    if (ok)
        v.push_back(0);
    for (int i=1; i<=n-m; i++)
    {
        ok=true;
        nr=(nr-s[i-1]+s[i+m-1])%mod;
        if (nr<0)
            nr+=mod;
        if (nr==nr1)
        {
            for (int j=0; j<m; j++)
                if (s[i+j]!=x[j])
                {
                    ok=false;
                    break;
                }
            if (ok)
                v.push_back(i);
        }
    }
    cout<<v.size()<<'\n';
    for (auto i : v)
        cout<<i<<" ";
}
/*
01234
ab
abava

*/