Pagini recente » Cod sursa (job #456719) | Cod sursa (job #1478079) | Cod sursa (job #2096145) | Cod sursa (job #2967751) | Cod sursa (job #1967964)
#include <iostream>
#include <fstream>
#include <vector>
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 prefix[NMax];
vector<int> sol;
int main() {
string str,patt;
in>>patt>>str;
int N = patt.size(),
M = str.size();
str = '\0' + str.substr(0,str.size());
patt = '\0' + patt.substr(0,patt.size());
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;
}