Pagini recente » Cod sursa (job #3253138) | Cod sursa (job #2730704) | Cod sursa (job #2254361) | Cod sursa (job #598236) | Cod sursa (job #2762619)
#include <fstream>
#include <string>
using namespace std;
const int MaxN = 2000010;
int pi[MaxN];
int sol[1010];
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
int main()
{
string A;
string B;
getline(cin, A);
getline(cin, B);
A = ' ' + A;
B = ' ' + B;
int q = 0;
pi[1] = 0;
for(int i = 2; i < (int)A.size(); ++i){
while(q && A[q+1] != A[i]){
q = pi[q];
}
if(A[q+1] == A[i]) ++q;
pi[i] = q;
}
int cnt = 0;
q = 0;
for(int i = 1; i < (int)B.size(); ++i){
while(q && A[q+1] != B[i]){
q = pi[q];
}
if(A[q+1] == B[i]) ++ q;
if(q == (int)A.size() - 1) {
q = pi[q];
++ cnt;
if(cnt <= 1000){
sol[cnt] = i-(int)A.size() + 1;
}
}
}
cout << cnt << '\n';
for(int i = 1; i <= min(1000, cnt); ++i){
cout << sol[i] << ' ';
}
return 0;
}