Pagini recente » Cod sursa (job #2232605) | Cod sursa (job #861711) | Cod sursa (job #92359) | Cod sursa (job #1662320) | Cod sursa (job #2986182)
#include <iostream>
#include <string.h>
#include <math.h>
using namespace std;
/*struct Nod
{
int value;
struct Nod *next;
}*List;*/
char stringA[2000001],stringB[2000001];
unsigned int prefix[2000001],appereances[1000];
/*void AddToList(Nod *&List,int val)
{
if(&List==NULL)
{
List->value=val;
List->next=NULL;
}
else
{
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)
{
while(List!=NULL)
{
printf("%u ",List->value);
List=List->next;
}
}
*/
unsigned int Minimum(unsigned int a,unsigned int b)
{
return (a>b) ? b:a;
}
void BuildPrefix(int length)
{
unsigned int j=0;
prefix[1]=0;
for(int i=2; i<=length; i++)
{
while(j>0 && stringA[j+1]!=stringA[i])
j=prefix[j];
if(stringA[j+1]==stringA[i])
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 && stringA[j+1]!=stringB[i])
j=prefix[j];
if(stringA[j+1]==stringB[i])
j=j+1;
if(j==lengthA)
{
num_appartitons++;
if(num_appartitons<=1000)
appereances[num_appartitons-1]=i-j+1;
j=prefix[j];
}
}
printf("%u\n",num_appartitons);
//PrintList(List);
for(unsigned int i=0; i<Minimum(1000,num_appartitons); i++)
printf("%u ",appereances[i]);
}
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
scanf("%s",stringA+1);
scanf("%s",stringB);
unsigned int lengthA=strlen(stringA+1);
unsigned int lengthB=strlen(stringB+1);
// stringA[lengthA+1]='\0';
// stringB[lengthB+1]='\0';
//strcpy(stringA+1,stringA);
//strcpy(stringB+1,stringB);
// stringA[0]=' ';
// stringB[0]=' ';
if(lengthA<=lengthB)
{
BuildPrefix(lengthA);
KMP(lengthA,lengthB);
}
return 0;
}