Pagini recente » Cod sursa (job #1638555) | Cod sursa (job #973111) | Cod sursa (job #2452818) | Cod sursa (job #693603) | Cod sursa (job #2626670)
#include <bits/stdc++.h>
using namespace std;
ifstream r("strmatch.in");
ofstream w("strmatch.out");
string a, b;
int p[2000005], n, m;
vector<int>f;
void pref()
{
p[1]=0;
int ans=0;
for(int i=2; i<=n; i++)
{
while(ans!=0 && a[ans+1]!=a[i])
{
ans=p[ans];
}
if(a[ans]==a[i])
{
ans++;
}
p[i]=ans;
}
}
void kmp()
{
int i=0, j=0;
while(j<m)
{
if(a[i]==b[j])
{
i++;
j++;
}
if(i==n)
{
f.push_back(j-i);
i=p[i-1];
}
else
{
if(j<m && a[i] != b[j])
{
if(i!=0)
{
i=p[i-1];
}
else
{
j++;
}
}
}
}
}
int main(void)
{
r>>a;
r>>b;
n=a.size(), m=b.size();
pref();
kmp();
w<<f.size()<<"\n";
for(int i=0; i<f.size(); i++)
{
w<<f[i]<<" ";
}
return 0;
}