Pagini recente » Cod sursa (job #999131) | Cod sursa (job #2327899) | Cod sursa (job #128556) | Cod sursa (job #243499) | Cod sursa (job #1814923)
#include <bits/stdc++.h>
#define NMAX 2000005
#define SMAX 1005
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
string A,B;
int P[NMAX],S[SMAX];
inline void make_prefix(){
int q = 0;
for(int i = 2; i <= A.size(); i++){
while(q && A[q + 1] != A[i])
q = P[q];
if(A[q + 1] == A[i])
q++;
P[i] = q;
}
}
int main()
{
ios :: sync_with_stdio(false);
fin.tie(NULL);
fin >> A >> B;
A = ' ' + A;
B = ' ' + B;
make_prefix();
int q = 0,m = A.size() - 1,n = 0;
for(int i = 1; i <= B.size(); i++){
while(q && A[q + 1] != B[i])
q = P[q];
if(A[q + 1] == B[i])
q++;
if(q == m){
q = P[q];
n++;
if(n <= 1000)
S[n] = i - m;
}
}
fout << min(n,1000) << "\n";
for(int i = 1; i <= min(n,1000); i++)
fout << S[i] << " ";
return 0;
}