Pagini recente » Cod sursa (job #463624) | Cod sursa (job #969809) | Cod sursa (job #757114) | Cod sursa (job #2776146) | Cod sursa (job #2458003)
#include <iostream>
#include <fstream>
#include <string>
using namespace std;
ifstream f ("strmatch.in");
ofstream g ("strmatch.out");
string a;
string b;
long long kmp[4000002];
int main()
{
f>>a>>b;
string c= a+b;
long long n=c.size();
kmp[0]=-1;
kmp[1]=0;
// g<<n;
long long x=-1;
for(long long i=1;i<=n;++i)
{
// for(int j=0;j<i;++j)
// g<<c.at(j);
// g<<" ";
while(x>-1 && c[x]!=c[i-1])
{
x=kmp[x];
}
++x;
kmp[i]=x;
// g<<kmp[i]<<"\n";
}
long long s=a.size();
long long nn=0;
for(long long i=2*s;i<=n;++i)
{
if(kmp[i]>=s)
{
nn++;
}
}
g<<nn<<"\n";
long long o=0;
for(long long i=2*s;i<=n;++i)
{
if(kmp[i]>=s)
{
g<<i-2*s<<" ";
o++;
if(o>=1000)
return 0;
}
}
return 0;
}