Pagini recente » Cod sursa (job #326069) | Cod sursa (job #493314) | Cod sursa (job #2017134) | Cod sursa (job #1698082) | Cod sursa (job #685656)
Cod sursa(job #685656)
#include <fstream>
#include <vector>
#include <cstring>
using namespace std;
const char InFile[]="strmatch.in";
const char OutFile[]="strmatch.out";
const int MaxN=2000111;
ifstream fin(InFile);
ofstream fout(OutFile);
int matches,P[MaxN];
char N[MaxN],M[MaxN];
vector<int> sol;
inline void prefix()
{
int len=strlen(N+1);
int k=0;
P[1]=0;
for(register int i=2;i<=len;++i)
{
while(k && N[i]!=N[k+1])
{
k=P[k];
}
if(N[i]==N[k+1])
{
++k;
}
P[i]=k;
}
}
inline void kmp()
{
int len2=strlen(N+1);
int len=strlen(M+1);
int k=0;
for(register int i=1;i<=len;++i)
{
while(k && M[i]!=N[k+1])
{
k=P[k];
}
if(M[i]==N[k+1])
{
++k;
}
if(k==len2)
{
++matches;
if(matches<=1000)
{
sol.push_back(i-len2);
}
}
}
}
int main()
{
fin>>N+1;
fin>>M+1;
fin.close();
prefix();
kmp();
fout<<matches<<"\n";
for(vector<int>::iterator it=sol.begin();it!=sol.end();++it)
{
fout<<*it<<" ";
}
fout.close();
return 0;
}