Pagini recente » Cod sursa (job #2578464) | Cod sursa (job #1784849) | Cod sursa (job #867594) | Cod sursa (job #335329) | Cod sursa (job #1896685)
#include <iostream>
#include <fstream>
#include <cstring>
#define NMAX 2000001
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);}
};
int pos[1000],dimA,dimB,nr,table[NMAX];
char a[NMAX],b[NMAX];
parser f("strmatch.in");
writer t("strmatch.out");
void build_table(){
int wPos=2,cnd=0;
table[0]=-1,table[1]=0;
while (wPos<dimA)
if (a[wPos-1]==a[cnd])
++cnd,
table[wPos]=cnd,
++wPos;
else
if (cnd>0)
cnd=table[cnd];
else
table[wPos]=0,
++wPos;
}
void kmp(){
int matchPos=0,wordPos=0;
while (matchPos+wordPos<dimB){
bool backtrack=true;
if (a[wordPos]==b[matchPos+wordPos]){
backtrack=false;
if (wordPos==dimA-1){
++nr;
if (nr<=1000)
pos[nr-1]=matchPos;
backtrack=true;
}
else
++wordPos;
}
if (backtrack)
if (table[wordPos]>-1)
matchPos+=wordPos-table[wordPos],
wordPos=table[wordPos];
else
wordPos=0,
++matchPos;
}
}
int main()
{
f>>a>>b;
dimA=strlen(a);
dimB=strlen(b);
if (dimA==dimB){
if (a==b)
t<<1<<"\n"<<0;
else
t<<0;
return 0;
}
build_table();
kmp();
t<<nr<<"\n";
for (int i=0;i<(nr<1000?nr:1000);++i)
t<<pos[i]<<" ";
return 0;
}