Pagini recente » Cod sursa (job #1532355) | Cod sursa (job #1343091) | Cod sursa (job #71663) | Cod sursa (job #851133) | Cod sursa (job #171753)
Cod sursa(job #171753)
#include<fstream.h>
ofstream g("strmatch.out");
#define nmax 2000100
#define rest 67
int nr, k, l, b, val, val2, s[1010];
char s1[nmax], s2[nmax];
void citire()
{
ifstream f("strmatch.in");
f.getline( s1, nmax);
f.getline( s2, nmax);
f.close();
}
void calc_s1()
{
int i;
b = 1;
k = strlen (s1);
for(i=k-1; i>=0; --i){
val = ( val + b * ( s1[i] % rest ) ) % rest;
b = ( b * rest ) % rest;
}
}
int cmp(int x)
{
int i;
for(i=0; i<k; ++i) if( s1[i] != s2[i+x-k+1] ) return 0;
return 1;
}
void rezolva()
{
int x, i;
x = b;
for(i=0; i<k; ++i){
val2 = ( val2 + x * ( s2[i] % rest ) ) % rest;
x = ( x / rest ) % rest;
}
if( val2 == val ) s[++nr] = 0;
l = strlen (s2);
for( ; i<l; ++i){
val2 = ( val2 - ( b * s2[l-k] ) % rest ) % rest;
val2 = ( val2 * rest ) % rest;
val2 = ( val2 + s2[i] ) % rest;
if( val2 == val ) if( cmp(i) ) s[++nr] = i - k + 1;
}
g<<nr<<'\n';
if ( nr < 1000 ) for(i=1; i<=nr; ++i) g<<s[i]<<' ';
else for(i=1; i<=1000; ++i) g<<s[i]<<' ';
}
int main()
{
citire();
calc_s1();
rezolva();
g.close();
return 0;
}