Pagini recente » Istoria paginii runda/oni-2012-ziua2-11-12 | Cod sursa (job #2477237) | Infoarena Monthly 2014 - Solutii Runda 6 | Istoria paginii runda/pixel_cup/clasament | Cod sursa (job #1760358)
/// Se dau doua siruri A si B formate din litere mici si mari ale alfabetului englez si din cifre.
/// Se cere gasirea tuturor aparitiilor sirului A ca subsecventa a sirului B.
#include <fstream>
#include <cstring>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
const int MAXL = 2000005;
const int MAXO = 1005;
int N, M;
char a[MAXL], b[MAXL];
int nr, rez[MAXO];
int p[MAXL];
void Read();
void KMP();
void Prefix();
void Write();
int main()
{
Read();
KMP();
Write();
fin.close();
fout.close();
return 0;
}
void Read()
{
fin.getline(a + 1, MAXL);
fin.getline(b + 1, MAXL);
N = strlen(a + 1);
M = strlen(b + 1);
}
void KMP()
{
int q = 0, i;
Prefix();
for ( i = 1; i <= M; i++ )
{
while ( q > 0 && a[q + 1] != b[i] )
q = p[q];
if ( a[q + 1] == b[i] )
++q;
if ( q == N )
{
q = p[N];
++nr;
if ( nr <= 1000 )
rez[nr] = i - N;
}
}
}
void Prefix()
{
int q = 0, i;
for ( i = 2; i <= N; i++ )
{
while ( q > 0 && a[q + 1] != a[i] )
q = p[q];
if ( a[q + 1] == a[i] )
++q;
p[i] = q;
}
}
void Write()
{
fout << nr << '\n';
for ( int i = 1; i <= min( 1000, nr ); i++ )
fout << rez[i] << ' ';
}