Pagini recente » Cod sursa (job #463340) | Cod sursa (job #1244584) | Cod sursa (job #2064302) | Cod sursa (job #1266940) | Cod sursa (job #1969086)
#include <iostream>
#include <fstream>
#include <vector>
#include <sstream>
#include <cstring>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
#define pb push_back
typedef long long ll;
const int NMax = 2e6 + 5;
int N,M;
int prefix[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 = 0;
for (int i=2;i<=N;++i) {
while (patt[i] != patt[k+1] && k != 0) {
k = prefix[k];
}
if (patt[i] == patt[k+1]) {
++k;
}
prefix[i] = k;
}
k = 0;
for (int i=1;i<=M;++i) {
while (str[i] != patt[k+1] && k != 0) {
k = prefix[k];
}
if (str[i] == patt[k+1]) {
++k;
if (k == N) {
sol.pb(i-N);
k = prefix[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;
}