Pagini recente » Cod sursa (job #2256063) | Cod sursa (job #2065062) | Cod sursa (job #1463808) | Cod sursa (job #2133118) | Cod sursa (job #219031)
Cod sursa(job #219031)
#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&&n<1000)
a[n++]=i-l1;
}
}
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");
g<<n<<endl;
for(int i=0;i<n;i++)
g<<a[i]<<" ";
}
int main()
{
citire();
kmp();
scriere();
return 0;
}