Pagini recente » Cod sursa (job #1287593) | Cod sursa (job #2901893) | Cod sursa (job #1280382) | Cod sursa (job #1228997) | Cod sursa (job #1896659)
#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>
#define MAXN 2000001
#define PRIME 73
#define MOD1 100007
#define MOD2 100021
using namespace std;
/**
`-.`'.-'
`-. .-'.
`-. -./\.- .-'
-. /_|\ .-
`-. `/____\' .-'.
`-. -./.-""-.\.- '
`-. /< (()) >\ .-'
- .`/__`-..-'__\' .-
,...`-./___|____|___\.-'.,.
,-' ,` . . ', `-,
,-' ________________ `-,
,'/____|_____|_____\
/ /__|_____|_____|___\
/ /|_____|_____|_____|_\
' /____|_____|_____|_____\
.' /__|_____|_____|_____|___\
,' /|_____|_____|_____|_____|_\
,,---''--...___...--'''--.. /../____|_____|_____|_____|_____\ ..--```--...___...--``---,,
'../__|_____|_____|_____|_____|___\
\ ) '.:/|_____|_____|_____|_____|_____|_\ ( /
)\ / ) ,':./____|_____|_____|_____|_____|_____\ ( \ /(
/ / ( ( /:../__|_____|_____|_____|_____|_____|___\ ) ) \ \
| | \ \ /.../|_____|_____|_____|_____|_____|_____|_\ / / | |
.-.\ \ \ \ '..:/____|_____|_____|_____|_____|_____|_____\ / / / /.-.
(= )\ `._.' | \:./ _ _ ___ ____ ____ _ _ _ _ _ _ _ __\ | `._.' /( =)
\ (_) ) \/ \ ( (_) /
\ `----' """""""""""""""""""""""""""""""""""""""""""""" `----' /
\ ____\__ __/____ /
\ (=\ \ / /-) /
\_)_\ \ / /_(_/
\ \ / /
) ) _ _ ( (
( (,-' `-..__ __..-' `-,) )
\_.-'' ``-..____ ____..-'' ``-._/
`-._ ``--...____...--'' _.-'
`-.._ _..-'
`-..__ FORTIS FORTUNA ADIUVAT __..-'
``-..____ ____..-''
``--...____...--''
*/
class parser{
public:
parser() {}
parser(const char *file_name){
input_file.open(file_name,ios::in | ios::binary);
input_file.sync_with_stdio(false);
index=0;
input_file.read(buffer,SIZE);}
inline parser &operator >>(char n[]){
for (;buffer[index]<'0' or buffer[index]>'z';inc());
int it=0;
for (;'0'<=buffer[index] and buffer[index]<='z';inc())
n[it++]=buffer[index];
n[it]='\0';
return *this;}
~parser(){
input_file.close();}
private:
fstream input_file;
static const int SIZE=0x400000;
char buffer[SIZE];
int index=0;
inline void inc(){
if(++index==SIZE)
index=0,input_file.read(buffer,SIZE);}
};
class writer{
public:
writer() {};
writer(const char *file_name){
output_file.open(file_name,ios::out | ios::binary);
output_file.sync_with_stdio(false);
index&=0;}
inline writer &operator <<(int target){
aux&=0;
n=target;
if (!n)
nr[aux++]='0';
for (;n;n/=10)
nr[aux++]=n%10+'0';
for(;aux;inc())
buffer[index]=nr[--aux];
return *this;}
inline writer &operator <<(const char *target){
aux&=0;
while (target[aux])
buffer[index]=target[aux++],inc();
return *this;}
~writer(){
output_file.write(buffer,index);output_file.close();}
private:
fstream output_file;
static const int SIZE=0x200000; ///2MB
int index,aux,n;
char buffer[SIZE],nr[24];
inline void inc(){
if(++index==SIZE)
index&=0,output_file.write(buffer,SIZE);}
};
char A[MAXN],B[MAXN];
int matches[MAXN];
parser f ("strmatch.in");
writer t ("strmatch.out");
int main()
{
f>>A>>B;
int dimA=strlen(A);
int dimB=strlen(B);
int P1=1,P2=1,hashA1=0,hashA2=0;
for (int i=0;i<dimA;++i){
hashA1=(hashA1*PRIME+A[i])%MOD1;
hashA2=(hashA2*PRIME+A[i])%MOD2;
if (i!=0)
P1=(P1*PRIME)%MOD1,
P2=(P2*PRIME)%MOD2;
}
if (dimA>dimB){
t<<0;
return 0;
}
int hash1=0,hash2=0;
for (int i=0;i<dimA;++i)
hash1=(hash1*PRIME+B[i])%MOD1,
hash2=(hash2*PRIME+B[i])%MOD2;
int nr=0;
if (hash1==hashA1 and hash2==hashA2)
/*matches.push_back(0)*/matches[0]=1,++nr;
for (int i=dimA;i<dimB/* and nr<1000*/;++i){
hash1=((hash1-(B[i-dimA]*P1)%MOD1+MOD1)*PRIME+B[i])%MOD1;
hash2=((hash2-(B[i-dimA]*P2)%MOD2+MOD2)*PRIME+B[i])%MOD2;
if (hash1==hashA1 and hash2==hashA2)
matches[i-dimA+1]=1,
++nr;
}
t<<nr<<"\n";
nr&=0;
for (int i=0;i<dimB and nr<1000;++i)
if (matches[i]){
++nr,
t<<i<<" ";}
return 0;
}