Pagini recente » Cod sursa (job #863196) | Cod sursa (job #2194962) | Cod sursa (job #335553) | Cod sursa (job #1085002) | Cod sursa (job #1973759)
#include <iostream>
#include <fstream>
#include <vector>
#include <string.h>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
#define pb push_back
typedef long long ll;
const int NMax = 2e6 + 5;
const int base = 73;
const int mod1 = 100003;
const int mod2 = 100005;
int N,M;
int pf[NMax];
char patt[NMax],str[NMax];
vector<int> sol;
int main() {
in>>(patt+1)>>(str+1);
N = strlen(patt+1);
M = strlen(str+1);
int k;
k = 0;
for (int i=2;i<=N;++i) {
while (patt[i] != patt[k+1] && k != 0) {
k = pf[k];
}
if (patt[i] == patt[k+1]) {
++k;
}
pf[i] = k;
}
k = 0;
for (int i=1;i<=M;++i) {
while (str[i] != patt[k+1] && k != 0) {
k = pf[k];
}
if (str[i] == patt[k+1]) {
++k;
if (k == N) {
sol.pb(i-N);
k = pf[k];
}
}
}
out<<sol.size()<<'\n';
int lim = (1000 < sol.size()) ? 1000 : sol.size();
for (int i=0;i<lim;++i) {
out<<sol[i]<<' ';
}
in.close();out.close();
return 0;
}