Cod sursa(job #3215241)

Utilizator ana_valeriaAna Valeria Duguleanu ana_valeria Data 14 martie 2024 19:22:06
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.83 kb
#include <fstream>
#include <cstring>
#define MAX 1000
#define MOD1 1000000007
#define MOD2 1000000009
#define BASE 62
using namespace std;
ifstream cin ("strmatch.in");
ofstream cout ("strmatch.out");
int ans[MAX + 10];
string s1, s2;
int turnToBase(char ch)
{
    if ('a' <= ch && ch <= 'z')
        return (ch - 'a');
    if ('A' <= ch && ch <= 'Z')
        return (ch - 'A' + 26);
    return (ch - '0' + 52);
}
int main()
{
    cin >> s1 >> s2;
    long long base_mod1 = 1, base_mod2 = 1;
    for (int i = 0; i < s1. size() - 1; i++)
    {
        base_mod1 = base_mod1 * BASE % MOD1;
        base_mod2 = base_mod2 * BASE % MOD2;
    }
    long long val_s1_mod1 = 0, val_s1_mod2 = 0, val_s2_mod1 = 0, val_s2_mod2 = 0;
    int cnt = 0;
    for (int i = 0; i < s1.size(); i++)
    {
        val_s1_mod1 = (val_s1_mod1 * BASE % MOD1 + turnToBase(s1[i])) % MOD1;
        val_s1_mod2 = (val_s1_mod2 * BASE % MOD2 + turnToBase(s1[i])) % MOD2;
        val_s2_mod1 = (val_s2_mod1 * BASE % MOD1 + turnToBase(s2[i])) % MOD1;
        val_s2_mod2 = (val_s2_mod2 * BASE % MOD2 + turnToBase(s2[i])) % MOD2;
    }
    if (val_s1_mod1 == val_s2_mod1 && val_s1_mod2 == val_s2_mod2)
    {
        cnt++;
        ans[cnt] = 0;
    }
    for (int i = s1.size(); i < s2.size(); i++)
    {
        val_s2_mod1 = ((val_s2_mod1 - base_mod1 * turnToBase(s2[i - s1.size()]) % MOD1 + MOD1) % MOD1 * BASE % MOD1 + turnToBase(s2[i])) % MOD1;
        val_s2_mod2 = ((val_s2_mod2 - base_mod2 * turnToBase(s2[i - s1.size()]) % MOD2 + MOD2) % MOD2 * BASE % MOD2 + turnToBase(s2[i])) % MOD2;
        if (val_s1_mod1 == val_s2_mod1 && val_s1_mod2 == val_s2_mod2)
        {
            cnt++;
            if (cnt <= 1000)
                ans[cnt] = i - s1.size() + 1;
        }
    }
    cout << cnt << '\n';
    for (int i = 1; i <= min(cnt, 1000); i++)
        cout << ans[i] << ' ';
    return 0;
}