Pagini recente » Cod sursa (job #1546828) | Cod sursa (job #3141956) | Cod sursa (job #2904363) | Cod sursa (job #1600930) | Cod sursa (job #3201148)
#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;
}