Cod sursa(job #3201148)

Utilizator EdyIordacheIordache Eduard EdyIordache Data 6 februarie 2024 22:00:24
Problema Potrivirea sirurilor Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.01 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <cstring>

using namespace std;

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

char pat[1001], str[1001];
int mod = 13751;

vector<int> sol;

void search() {
    int n = strlen(pat), m = strlen(str);
    int h = 1;
    int d = 100;

    for (int i = 1; i < n; i++) {
        h = (h*d) % mod;
    }

    int t = 0, p = 0;
    for (int i = 0; i < n; i++) {
        p = (p*d + pat[i]) % mod;
        t = (t*d + str[i]) % mod;
    }

    for (int i = 0; i <= m - n + 1; i++) {
        if (p == t) {
            bool ok = true;
            for (int j = 0; j < n && ok; j++) {
                if (pat[j] != str[i + j - 1]) ok = false;
            }

            if (ok) sol.push_back(i - 1);
        }
        else {
            t = (d * (t - str[i]*h) + str[i + n]) % mod;

            if (t < 0) t += mod;
        }
    }
}

int main() {
    fin>>pat>>str;

    search();

    fout<<sol.size()<<endl;
    for (auto i:sol) fout<<i<<" ";

    return 0;
}