Pagini recente » Cod sursa (job #2413445) | Cod sursa (job #1383329) | Cod sursa (job #3283977) | Cod sursa (job #561045) | Cod sursa (job #2765680)
#include <bits/stdc++.h>
#define NMAX 2000005
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
char a[NMAX], b[NMAX];
int lps[NMAX], nr, n, m;
vector <int> ans;
void init()
{
int l = 0;
lps[1] = 0;
for(int i = 2; i <= n; i++)
{
while(l && a[l + 1] != a[i])
l = lps[l];
if(a[i] == a[l + 1])
l++;
lps[i] = l;
}
}
void kmp()
{
init();
int l = 0;
for(int i = 1; i <= m; i++)
{
while(l && a[l + 1] != b[i])
l = lps[l];
if(a[l + 1] == b[i])
l++;
if(l == n)
{
l = lps[n];
nr++;
if(nr <= 1000)
ans.push_back(i - n);
}
}
}
int main()
{
f >> a + 1 >> b + 1;
n = strlen(a + 1);
m = strlen(b + 1);
kmp();
g << ans.size() << "\n";
for(auto k : ans)
g << k << " ";
return 0;
}