Pagini recente » Cod sursa (job #2540681) | Cod sursa (job #445410) | Cod sursa (job #1663481) | Cod sursa (job #2613062) | Cod sursa (job #2466079)
#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 P[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 = P[k];
if(X[k + 1] == X[i])
++k;
P[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 = P[k];
if(X[k + 1] == Y[i])
++k;
if(k == 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;
}