Pagini recente » Cod sursa (job #2642025) | Cod sursa (job #2621933) | Cod sursa (job #3293683) | Cod sursa (job #2475200) | Cod sursa (job #1629060)
#include <bits/stdc++.h>
#define NMax 20000005
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
char x[NMax],y[NMax];
vector<int> ANS;
int pi[NMax];
int X,Y;
void prefix(){
int k = 0;
pi[0] = 0;pi[1] = 0;
X = strlen(x + 1);
for(int i = 2; i <= X; ++i){
while(k > 0 && x[k + 1] != x[i])
k = pi[k];
if(x[k + 1] == x[i])
++k;
pi[i] = k;
}
}
void potrivire(){
int k = 0;
X = strlen(x + 1); Y = strlen(y + 1);
for(int i = 1; i <= Y; ++i){
while(k > 0 && x[k + 1] != y[i])
k = pi[k];
if(x[k + 1] == y[i])
++k;
if(k == X)
ANS.push_back(i - X + 1);
}
}
int main()
{
f.getline(x + 1,NMax);
f.getline(y + 1,NMax);
prefix();
potrivire();
g << ANS.size()<<"\n";
int w = 0;
if(ANS.size() > 1000)
w = 1000;
else
w = ANS.size();
for(int i = 0; i < w; ++i){
g << ANS[i] - 1 <<" ";
}
return 0;
}