Pagini recente » Borderou de evaluare (job #908508) | Cod sursa (job #1407061) | Cod sursa (job #2314394) | Cod sursa (job #3165193) | Cod sursa (job #2466080)
#include <fstream>
#include <cstring>
#include <vector>
#define MAX 2000005
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char X[MAX], Y[MAX];
int Pi[MAX];
vector<int> v;
void make_prefix(){
int lg = strlen(X);
--lg;
int k = 0;
for(int i = 2; i <= lg; ++i){
while(k > 0 && X[k + 1] != X[i])
k = Pi[k];
if(X[k + 1] == X[i])
++k;
Pi[i] = k;
}
}
void kmp(){
int lg = strlen(Y) - 1;
int lg2 = strlen(X) - 1;
int k = 0;
for(int i = 1; i <= lg; ++i){
while(k > 0 && X[k + 1] != Y[i])
k = Pi[k];
if(X[k + 1] == Y[i])
++k;
if(k == lg2){
k = Pi[lg2];
if(v.size() < 1000)
v.push_back(i - lg2);
else return;
}
}
}
int main()
{
fin >> X >> Y;
int lg1 = strlen(X);
int lg2 = strlen(Y);
for(int i = lg1 - 1; i >= 0; --i)
X[i + 1] = X[i];
for(int i = lg2 - 1; i >= 0; --i)
Y[i + 1] = Y[i];
make_prefix();
kmp();
fout << v.size() << '\n';
for(int i = 0; i < v.size(); ++i)
fout << v[i] << ' ';
fout << '\n';
return 0;
}