Pagini recente » Cod sursa (job #829865) | Cod sursa (job #1893637) | Cod sursa (job #2192943) | Cod sursa (job #1831956) | Cod sursa (job #1360899)
#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[100005];
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+1;i++)
{
j=0;
match=false;
while(code[i+j]==key[j] && j<n)
{
j++;
match=true;
if(j==n)
{
k++;
poz[k]=i;
}
}
if(match==true)
i+=j-PMT[j-1]-1;
}
y<<k+1<<'\n';
if(k>999)
k=999;
for(i=0;i<=k;i++)
y<<poz[i]<<' ';
y<<'\n';
return 0;
}