Pagini recente » Cod sursa (job #1646893) | Cod sursa (job #2885733) | Cod sursa (job #219245) | Cod sursa (job #998010) | Cod sursa (job #1641213)
#include <fstream>
#include <cstring>
using namespace std;
ifstream fi("strmatch.in");
ofstream fo("strmatch.out");
#define mx 2000001
#define prim 666013
char c[mx], s[mx];
int rez[1000], nr, n, m;
int exp(int b,int p){
int r;
r = 1;
while( p > 0 ){
if ( p % 2 == 1 )
r = (r * b) % prim;
b = (b * b) % prim;
p /= 2;
}
return r;
}
int check( int poz ){
int j;
j = 0;
while( s[poz] == c[j] && j < n ){
j++;
poz++;
}
if( j == n )
return 1;
else
return 0;
}
int main()
{
int p, t, dc, ds, pow, r, a, ok, poz, i;
fi.get(c,mx);
fi.get();
fi.get(s,mx);
//fo << c << "\n" << s;
n = strlen(c);
p = 0;
t = 0;
for( i = 0; i < n; i++ ){
if( islower(c[i]) ){
dc = c[i] - 'a';
}
else{
dc = c[i] - 'A' + 26;
}
if( dc > 0 ){
pow = (exp(51,n-i-1) * dc) % prim;
p = (p + pow) % prim;
}
if( islower(s[i]) ){
ds = s[i] - 'a';
}
else{
ds = s[i] - 'A' + 26;
}
if( ds > 0 ){
pow = (exp(51,n-i-1) * ds) % prim;
t = (t + pow) % prim;
}
}
nr = 0;
if( p == t )
if( check(0) == 1 )
rez[nr++] = 0;
m = strlen(s);
for( i = n; i < m; i++ ){
poz = i - n;
if( islower(s[poz]) )
ds = s[poz] - 'a';
else
ds = s[poz] - 'A' + 26;
//if( ds > 0 ){
pow = (exp(51,n-1) * ds) % prim;
t = (t - pow) % prim;
// }
if( islower(s[i]) )
ds = s[i] - 'a';
else
ds = s[i] - 'A' + 26;
t = (t * 51) % prim;
t = (t + ds) % prim;
if( t == p )
if(check(poz + 1) == 1)
rez[nr++] = poz + 1;
}
fo << nr << "\n";
for( i = 0; i < nr && i < 1000; i++ )
fo << rez[i] << " ";
return 0;
}