Pagini recente » Cod sursa (job #301301) | Cod sursa (job #2679557) | Cod sursa (job #3267201) | Cod sursa (job #3243854) | Cod sursa (job #2083061)
#include <iostream>
#include <cstdio>
using namespace std;
const int MOD = 1000000007;
const int d = 256;
int main()
{
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(0);
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
string pattern;
cin >> pattern;
string text;
cin >> text;
int h = 1;
for (int i = 1; i < pattern.size(); i++)
h = (1LL * h * d) % MOD;
int pattern_hash = 0;
int hash = 0;
for (int i = 0; i < pattern.size() && i < text.size(); i++)
{
pattern_hash = ((1LL * pattern_hash * d) + pattern[i]) % MOD;
hash = ((1LL * hash * d) + text[i]) % MOD;
}
int counter = 0;
int matches_nr = 0;
int match[1002];
for (int i = 0; i <= (int)text.size() - (int)pattern.size(); i++)
{
if (hash == pattern_hash)
{
int j = 0;
for (; j < pattern.size(); j++)
{
if (text[i + j] != pattern[j])
break;
}
if (j == pattern.size())
{
matches_nr++;
if (counter < 1000)
match[counter++] = i;
}
}
//rehash
hash = (d * (hash - 1LL * h * text[i])) % MOD + text[i + pattern.size()];
if (hash < 0)
hash += MOD;
if (hash >= MOD)
hash -= MOD;
}
cout << matches_nr << '\n';
for (int i = 0; i < matches_nr && i < 1000; i++)
cout << match[i] << ' ';
cout << '\n';
return 0;
}