Pagini recente » Cod sursa (job #640106) | Cod sursa (job #229685) | Cod sursa (job #1429490) | Cod sursa (job #3223782) | Cod sursa (job #2301561)
#include <fstream>
#include <cstring>
#define nmax 2000005
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
int poz[1002];
int t[nmax];
char s[nmax];
char z[nmax];
int c , n, m;
void constr()
{
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[m+1]=NULL;
constr();
cauta();
g<< c <<'\n';
for (int i = 1 ; i <= min(c,1000); i ++ )
g <<poz[i]<<" " ;
return 0;
}