Pagini recente » Cod sursa (job #183881) | Cod sursa (job #798872) | Statistici Popa Iarina (popaiarina) | Monitorul de evaluare | Cod sursa (job #961273)
Cod sursa(job #961273)
#include<fstream>
#include<cstring>
#include<vector>
#define MAX_SIZE 2000005
#define get_min(a,b) ((a)>(b)?(a):(b))
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
typedef vector<int>::iterator IT;
char sir1[MAX_SIZE],sir2[MAX_SIZE];
int N,M,pref[MAX_SIZE];
vector<int> Sol;
void Read ( void )
{
sir1[0]=' ';
sir2[0]=' ';
f>>(sir1+1)>>(sir2+1);
M=strlen(sir1)-1;
N=strlen(sir2)-1;
f.close();
}
void MakePrefix( void )
{
pref[1]=0;
for(int i(2) ,q(0) ; i <= M ; ++i )
{
while(q && sir1[q+1] != sir1[i] )
q=pref[q];
if(sir1[q+1] == sir1[i] )
++q;
pref[i]=q;
}
}
void KMP ( void )
{
for(int i(1),q(0) ; i <= N ; ++i )
{
while(q && sir1[q+1] != sir2[i] )
q=pref[q];
if( sir1[q+1] == sir2[i] )
++q;
if( q == M )
{
q=pref[M];
Sol.push_back(i-M);
}
}
}
void Solve ( void )
{
MakePrefix();
KMP();
}
void Write ( void )
{
g<<Sol.size()<<"\n";
int cnt(0);
for(IT it=Sol.begin() ; cnt <= 1000 && it!= Sol.end() ; g<<*it<<" ",++it,++cnt);
g.close();
}
int main ( void )
{
Read();
Solve();
Write();
return 0;
}