Pagini recente » Cod sursa (job #1289403) | Cod sursa (job #1610544) | Cod sursa (job #1262114) | Cod sursa (job #1234024) | Cod sursa (job #1971471)
#include <iostream>
#include <fstream>
#include <vector>
#include <cstring>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
#define pb push_back
#define ui unsigned int
const ui NMax = 2e6 + 5;
const ui base = 73;
int N,M;
char patt[NMax],str[NMax];
vector<int> sol;
int main() {
in>>(patt+1)>>(str+1);
N = strlen(patt+1);
M = strlen(str+1);
ui pattHash,strHash,pw;
pattHash = strHash = 0;
pw = 1;
for (int i=1;i<=N;++i) {
pattHash = pattHash * base + patt[i] * base;
strHash = strHash * base + str[i] * base;
pw *= base;
}
if (pattHash == strHash) {
sol.pb(0);
}
for (int i=N+1;i<=M;++i) {
strHash = (strHash - str[i-N] * pw) * base + str[i] * base;
if (pattHash == strHash) {
sol.pb(i-N);
}
}
out<<sol.size()<<'\n';
int lim = (1000 < sol.size()) ? 1000 : sol.size();
for (int k=0;k < lim;++k) {
out<<sol[k]<<' ';
}
in.close();out.close();
return 0;
}