Pagini recente » Cod sursa (job #320145) | Cod sursa (job #375744) | Cod sursa (job #394865) | Cod sursa (job #1773540) | Cod sursa (job #2065869)
#include <fstream>
#include <cstring>
#define nmax 2000005
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int poz[1002];
int t[nmax];
char s[nmax];
char 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()
{
fin.getline(z,nmax);
fin.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[m+1]=NULL;
constr_vect_temp();
cauta();
fout<<c<<"\n";
for(int i=1;i<=min(c,1000);i++)
{
fout<<poz[i]<<" ";
}
return 0;
}