Pagini recente » Cod sursa (job #2938649) | Cod sursa (job #2069430) | Cod sursa (job #87425) | Cod sursa (job #2660008) | Cod sursa (job #2985715)
#include <iostream>
#include <string.h>
using namespace std;
struct Nod
{
int value;
struct Nod *next;
}*List;
char stringA[2000001],stringB[2000001];
unsigned int prefix[2000001];
void AddToList(Nod *&List,int val)
{
Nod *p=new Nod;
p->value=val;
p->next=List;
// p->next=NULL;
// struct Nod *nod_current=List;
//while(nod_current->next!=NULL)
// nod_current=nod_current->next;
//nod_current->next=p;
List=p;
}
void PrintList(Nod *&List)
{
unsigned int num=0;
while(List!=NULL && num+1<=1000)
{
printf("%u ",List->value);
List=List->next;
num++;
}
}
void BuildPrefix(int length)
{
unsigned int j=0;
prefix[1]=0;
prefix[0]=0;
for(int i=2; i<=length; i++)
{
while(j>0 && stringA[i]!=stringA[j+1])
j=prefix[j];
if(stringA[i]==stringA[j+1])
j=j+1;
prefix[i]=j;
}
}
void KMP(unsigned int lengthA,unsigned int lengthB)
{
unsigned int j=0,num_appartitons=0;
for(unsigned int i=1; i<=lengthB; i++)
{
while(j>0 && stringB[i]!=stringA[j+1])
j=prefix[j];
if(stringB[i]==stringA[j+1])
j++;
if(j==lengthA)
{
num_appartitons++;
AddToList(List,i-j);
j=prefix[lengthA];
}
}
printf("%u\n",num_appartitons);
PrintList(List);
}
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
scanf("%s",stringA);
scanf("%s",stringB);
unsigned int lengthA=strlen(stringA);
unsigned int lengthB=strlen(stringB);
stringA[lengthA+1]='\0';
stringB[lengthB+1]='\0';
strcpy(stringA+1,stringA);
strcpy(stringB+1,stringB);
stringA[0]=' ';
stringB[0]=' ';
BuildPrefix(lengthA);
KMP(lengthA,lengthB);
return 0;
}