Pagini recente » Cod sursa (job #511124) | Cod sursa (job #1156378) | Cod sursa (job #3236578) | Cod sursa (job #245172) | Cod sursa (job #2808326)
#include <bits/stdc++.h>
using namespace std;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
string A , B;
int z [(int)4e6 + 5] , ans [1001];
int main()
{
fin >> A >> B;
B = A + '|' + B;
int l , r;
l = r = 0;
for(int i = 1 ; i < B.size () ; ++ i){
if (i <= r)
z [i] = min (z [i - l] , r - i + 1);
while (i + z [i] < B.size () && B [z [i]] == B [i + z [i]])
++ z [i];
if (i + z [i] - 1 > r){
r = i + z [i] - 1;
l = i;
}
}
int cnt (0);
for(int i = A.size () + 1 ; i < B.size (); ++ i)
if (z [i] == A.size ()){
++ cnt;
if (cnt <= 1000)
ans [cnt] = i - A.size () - 1;
}
fout << cnt << '\n';
for(int i = 1 ; i <= cnt ; ++ i)
fout << ans [i] << ' ';
return 0;
}