Pagini recente » Cod sursa (job #3299787) | Cod sursa (job #825040) | Cod sursa (job #2210180) | Cod sursa (job #877440) | Cod sursa (job #3321072)
#include <bits/stdc++.h>
#define NMAX 2000005
#define ll long long
std::ifstream f("strmatch.in");
std::ofstream g("strmatch.out");
using namespace std;
int n, m, ans;
string a, b;
int lps[NMAX], sol[NMAX];
void init()
{
int i=1, lg=0;
while(i<n)
{
if(a[i]==a[lg])lg++,lps[i++]=lg;
else
{
if(lg) lg=lps[lg-1];
else lps[i++]=0;
}
}
}
void kmp()
{
int i=0, lg=0;
while(i<m)
{
if(b[i]==a[lg])
{
i++;
lg++;
if(lg==n)sol[++ans]=i-lg, lg=lps[lg-1];
}
else
{
if(lg) lg=lps[lg-1];
else i++;
}
}
g << ans << '\n';
for(int i=1; i<=min(ans, 1000); i++)g << sol[i] << " ";
}
int main()
{
f >> a;
f.get();
f >> b;
n=a.size(), m=b.size();
init();
kmp();
}