Pagini recente » Cod sursa (job #1157093) | Cod sursa (job #1825080) | Cod sursa (job #2796919) | Cod sursa (job #2888503) | Cod sursa (job #219034)
Cod sursa(job #219034)
#include <fstream>
#include <string>
#define nm 2000003
using namespace std;
char s1[nm],s2[nm];
int a[1002],n;
int pre[nm];
void prefix()
{
int l=strlen(s1);
int k=0;
for(int i=2;i<l;i++)
{
while(k&&s1[k+1]!=s1[i])
k=pre[k];
if(s1[k+1]==s1[i])
k++;
pre[i]=k;
}
}
void kmp()
{
int l2=strlen(s2);
int l1=strlen(s1)-1;
int k=0;
for(int i=1;i<l2;i++)
{
while(k&&s1[k+1]!=s2[i])
k=pre[k];
if(s1[k+1]==s2[i])
k++;
if(k==l1)
{
if(n<1000)
a[n]=i-l1;
n++;
}
}
}
void init()
{
if(s1[strlen(s1)-1]=='\n')
s1[strlen(s1)-1]=0;
if(s2[strlen(s2)-1]=='\n')
s2[strlen(s2)-1]=0;
int l1=strlen(s1);
int l2=strlen(s2);
for(int i=l1;i>0;i--)
s1[i]=s1[i-1];
s1[0]=' ';
for(int i=l2;i>0;i--)
s2[i]=s2[i-1];
s2[0]=' ';
}
void citire()
{
ifstream f("strmatch.in");
f.getline(s1,nm);
f.getline(s2,nm);
f.close();
init();
prefix();
}
void scriere()
{
ofstream g("strmatch.out");
int l=n<1000?n:1000;
g<<n<<endl;
for(int i=0;i<l;i++)
g<<a[i]<<" ";
}
int main()
{
citire();
kmp();
scriere();
return 0;
}