Mai intai trebuie sa te autentifici.
Cod sursa(job #2772628)
| Utilizator | Data | 1 septembrie 2021 22:13:19 | |
|---|---|---|---|
| Problema | Potrivirea sirurilor | Scor | 16 |
| Compilator | cpp-64 | Status | done |
| Runda | Arhiva educationala | Marime | 1.06 kb |
#include<bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
#define MAXN 2000005
#define MOD 101
char pattern[MAXN],str[MAXN];
int pattern_length , str_length, match[MAXN], matches;
int main() {
fin >> pattern >> str;
str_length = strlen(str);
pattern_length = strlen(pattern);
if (pattern_length > str_length) {
fout << 0;
return 0;
}
int base = 256, hash1 = 0 , hash2 = 0, r = 1;
for (int i = 0; i < pattern_length; i++) {
hash1 = (hash1 * base + pattern[i]) % MOD;
hash2 = (hash2 * base + str[i]) % MOD;
if (i != 0)
r = (r * base) % MOD;
}
if (hash1 == hash2)
match[++matches] = 1;
for (int i = pattern_length; i < str_length; i++) {
hash2 = (((hash2 - r * str[i - pattern_length]) % MOD + MOD) * base + str[i]) % MOD;
if (hash2 == hash1)
match[++matches] = i - pattern_length + 1;
}
fout << matches << "\n";
for (int i = 1; i <= matches; i++)
fout << match[i] << " ";
}
