Cod sursa(job #2861450)

Utilizator anghelmrsmanghel eduard anghelmrsm Data 3 martie 2022 23:22:25
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.19 kb
#include <bits/stdc++.h>
using namespace std;

ifstream ci("strmatch.in");
ofstream cou("strmatch.out");
#define d 256

vector <int> v;
void search(char pat[], char txt[], int q)
{
    int M = strlen(pat);
    int N = strlen(txt);
    int i, j;
    int p = 0;
    int t = 0;
    int h = 1;
    for (i = 0; i < M - 1; i++)
        h = (h * d) % q;
    for (i = 0; i < M; i++)
    {
        p = (d * p + pat[i]) % q;
        t = (d * t + txt[i]) % q;
    }
    for (i = 0; i <= N - M; i++)
    {
        bool flag = true;
        if ( p == t )
        {
            for (j = 0; j < M; j++)
            {
                if (txt[i+j] != pat[j])
                {
                    flag = false;
                    break;
                }
            }
            if(flag)
                v.push_back(i);
        }
        if ( i < N-M )
        {
            t = (d*(t - txt[i]*h) + txt[i+M])%q;
            if (t < 0)
                t = (t + q);
        }
    }
}
char pat[2000001],txt[2000001];
int main()
{
    ci>>pat;
    ci>>txt;
    int q = 101;
    search(pat, txt, q);
    cou<<v.size()<<'\n';
    for (auto i : v)
        cou<<i<<" ";
    return 0;
}