Pagini recente » Cod sursa (job #2799112) | Cod sursa (job #1696991) | Cod sursa (job #2606871) | Cod sursa (job #160197) | Cod sursa (job #2351556)
/// 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, MAXL);
fin.getline(b, MAXL);
N = strlen(a);
M = strlen(b);
}
void KMP()
{
int q = -1, i;
Prefix();
for ( i = 0; i < M; i++ )
{
while ( q != -1 && a[q + 1] != b[i] )
q = p[q];
if ( a[q + 1] == b[i] )
++q;
if ( q == N - 1 )
{
q = p[N - 1];
++nr;
if ( nr <= 1000 )
rez[nr] = i - N + 1;
}
}
}
void Prefix()
{
int q = -1, i;
p[0] = -1;
for ( i = 1; i < N; i++ )
{
while ( q != -1 && 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] << ' ';
}