Pagini recente » Cod sursa (job #3135319) | Cod sursa (job #2432348) | Cod sursa (job #2458927) | Cod sursa (job #214321) | Cod sursa (job #3201154)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
#define NMAX 2000001
char pat[NMAX], str[NMAX];
int mod = 1000000013;
vector<int> sol;
void search() {
int n = strlen(pat), m = strlen(str);
int h = 1;
int d = 257;
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 if (i <= m - n){
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;
}