Pagini recente » Cod sursa (job #2445634) | Cod sursa (job #1167186) | Cod sursa (job #736200) | Cod sursa (job #319321) | Cod sursa (job #2288131)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char A[2000005], B[2000005];
int n, m, k, pi[2000005], v[1050], ans;
//vector <int> v;
int main()
{
fin >> A+1;
fin >> B+1;
n = strlen(A+1);
m = strlen(B+1);
k = 0;
for(int i = 2; i <= n; i++)
{
while(k>0 && A[i] != A[k+1])
k = pi[k];
if(A[k+1] == A[i])
k++;
pi[i] = k;
}
k = 0;
for(int i = 1 ; i <= m; i++)
{
while(k>0 && A[k+1] != B[i])
k = pi[k];
if(A[k+1] == B[i])
k++;
if(k == n)
{
k = pi[n];
ans++;
if(ans<=1000)
v[ans] = i-n;
}
}
fout << ans << '\n';
for(int i = 1; i <= min(ans, 1000); i++)
fout << v[i] << " ";
return 0;
}