Pagini recente » Cod sursa (job #2859269) | Cod sursa (job #3138832) | Cod sursa (job #2625725) | Cod sursa (job #2052303) | Cod sursa (job #1360871)
#include <fstream>
#include <cstring>
#define nMax 2000000
using namespace std;
ifstream x ("strmatch.in");
ofstream y ("strmatch.out");
char key[nMax],code[nMax];
int PMT[nMax];
int poz[1000];
void generate_PMT(int n)
{
int i;
for(i=1;i<n;i++)
if(key[i]==key[PMT[i-1]])
PMT[i]=PMT[i-1]+1;
else
if(key[i]==key[0])
PMT[i]=1;
/*
y<<key;
y<<'\n';
for(i=0;i<n;i++)
y<<PMT[i];
y<<'\n';
*/
}
int main()
{
int i;
x>>key;
x>>code;
generate_PMT(strlen(key));
bool match;
int n=strlen(key);
int N=strlen(code);
int j,k=-1;
for(i=0;i<N-n;i++)
{
j=0;
match=false;
while(code[i+j]==key[j] && j<n)
{
j++;
match=true;
if(j==n && k<999)
{
k++;
poz[k]=i;
}
}
if(match==true)
i+=j-PMT[j-1]-1;
}
y<<k+1<<'\n';
for(i=0;i<=k;i++)
y<<poz[i]<<' ';
y<<'\n';
return 0;
}