Pagini recente » Cod sursa (job #638734) | Cod sursa (job #592575) | Cod sursa (job #526791) | Cod sursa (job #1385458) | Cod sursa (job #1965051)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
string a, b;
int n, m, pi[2000010], i, j, nr, sol[1010];
int main()
{
fin >> a >> b;
n = a.size();
m = b.size();
i = 1; j = 0;
for(i = 1; i < n; i++){
while(j > 0 && a[j] != a[i])
j = pi[j - 1];
if(a[j] == a[i])
j++;
pi[i] = j;
//cout << pi[i] << ' ';
}
j = 0;
for(i = 0; i < m; i++){
while(j > 0 && a[j] != b[i])
j = pi[j - 1];
if(a[j] == b[i])
j++;
if(j == n){
nr++;
j = pi[j - 1];
if(nr <= 1000) sol[nr] = i - n + 1;
}
}
fout << nr << '\n';
for(i = 1; i <= min(nr, 1000); i++)
fout << sol[i] << ' ';
return 0;
}