Pagini recente » Cod sursa (job #2400473) | Cod sursa (job #1363813) | Cod sursa (job #681378) | Cod sursa (job #3139559) | Cod sursa (job #1607704)
#include <fstream>
#include <cstring>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char s[2000002], t[2000002];
int pi[2000002], nr, sol[1010];
void Precalculare()
{
int i, m=strlen(t), k;
pi[0]=0;
k=0;
for(i=1; i<m; i++)
{
if(t[i]==t[k])
k++;
else
{
while(k>0&&t[k]!=t[i])
k=pi[k-1];
if(t[k]==t[i]) k++;
}
pi[i]=k;
}
}
void KMP()
{
int n=strlen(s), m=strlen(t), i, k=0;
for(i=0; i<n; i++)
{
if(s[i]==t[k]) k++;
else
{
while(k>0 && t[k]!=s[i])
k=pi[k-1];
if(t[k]==s[i]) k++;
}
//d[i]=k;
if(k==m)
{
nr++;
if(nr<=1000)
sol[nr]=i-m+1;
}
}
}
int main()
{
int i;
fin>>t>>s;
Precalculare();
KMP();
fout<<nr<<"\n";
if(nr<=1000)
for(i=1; i<=nr; i++)
fout<<sol[i]<<" ";
else for(i=1; i<=1000; i++)
fout<<sol[i]<<" ";
return 0;
}