Pagini recente » Cod sursa (job #246119) | Cod sursa (job #570944) | Cod sursa (job #434769) | Cod sursa (job #2048746) | Cod sursa (job #1976931)
#include <iostream>
#include <fstream>
#include <vector>
#include <cstring>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
#define pb push_back
typedef long long ll;
const int strMax = 2e6 + 5;
int N,M;
char patt[strMax],str[strMax];
int pf[strMax];
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+1);
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;
}