Pagini recente » Cod sursa (job #2603947) | Cod sursa (job #2603960) | Cod sursa (job #2509032) | Cod sursa (job #1932522) | Cod sursa (job #3293701)
#include <fstream>
#include <cstring>
#include <vector>
using namespace std;
ifstream fcin("strmatch.in");
ofstream fout("strmatch.out");
string a,b;
int lps[2001001];
inline void precalc(const string &s)
{
int i=1, j=0;
lps[1]=0;
while(i<s.size())
{
if(s[i]==s[j])
{
j++;
lps[i]=j;
i++;
}
else
{
if(j!=0)
{
j=lps[j-1];
}
else
{
i++;
}
}
}
}
inline void kmp(const string &a, const string &b)
{
vector <int> v;
int i=0, j=0;
while(i<b.size())
{
if(b[i]==a[j])
{
i++;
j++;
}
else
{
if(j!=0)
{
j=lps[j-1];
}
else
{
i++;
}
}
if(j==a.size())
{
v.push_back(i-j);
}
}
fout<<v.size()<<'\n';
for(int i=0; i<min(1000,(int)v.size()); i++)
fout<<v[i]<<" ";
}
int main()
{
fcin>>a>>b;
precalc(a);
kmp(a,b);
return 0;
}