Pagini recente » Cod sursa (job #2257816) | Cod sursa (job #2706634) | Cod sursa (job #1911732) | Cod sursa (job #1285635) | Cod sursa (job #2301560)
#include <fstream>
#include<cstring>
#define nmax 2000005
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
int poz[1002],t[nmax];
char s[nmax],z[nmax];
int c=0,n,m;
void constr_vect_temp()
{
int j=0;
for(int i=2;z[i]!=NULL;i++)
{
while(z[j+1]!=z[i]&&j)
j=t[j];
if(z[j+1]==z[i])
j++;
t[i]=j;
}
}
void cauta()
{
int j=0;
int m=strlen(z);
for(int i=1;s[i]!=NULL;i++)
{
while(z[j+1]!=s[i]&&j)
j=t[j];
if(z[j+1]==s[i])
j++;
if(j==m-1)
{
j=t[j];
c++;
if(c<=1000)
poz[c]=i-m+1;
}
}
}
int main()
{
f.getline(z,nmax);
f.getline(s,nmax);
int n=strlen(s);
int m=strlen(z);
for(int i=n;i>=1;i--)
s[i]=s[i-1];
for(int j=m;j>=1;j--)
z[j]=z[j-1];
s[0]=' ';
z[0]=' ';
s[n+1]=NULL;
z[n+1]=NULL;
constr_vect_temp();
cauta();
g<<c<<"\n";
for(int i=1;i<=min(c,1000);i++)
{
g<<poz[i]<<" ";
}
return 0;
}