Pagini recente » Cod sursa (job #1448797) | Cod sursa (job #977305) | Cod sursa (job #790052) | Cod sursa (job #2389662) | Cod sursa (job #2716552)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char a[2000002];
char b[2000002];
int pi[2000002];
vector<int> sol;
int main()
{
fin >> (a+1) >> (b+1);
int n = strlen(a+1);
int m = strlen(b+1);
int j = 0;
for(int i = 2; i <= n; i ++)
{
while(j > 0 && a[i] != a[j+1])
{
j = pi[j];
}
if(a[i] == a[j + 1])
j++;
pi[i] = j;
}
j = 0;
int ans = 0;
for(int i = 2; i <= m; i ++)
{
while(j > 0 && b[i] != a[j + 1])
{
j = pi[j];
}
if(b[i] == a[j + 1])
j++;
if(j == n)
{
sol.push_back(i - n);
}
}
ans = sol.size();
fout << ans << '\n';
ans = min(ans,1000);
for(int i = 0; i < ans; i ++)
fout << sol[i] << ' ';
return 0;
}