Pagini recente » Cod sursa (job #321447) | Cod sursa (job #580713) | Cod sursa (job #1713605) | Cod sursa (job #2466515) | Cod sursa (job #2164627)
#include <bits/stdc++.h>
#define N 100005
using namespace std;
ifstream fin( "strmatch.in" );
ofstream fout( "strmatch.out" );
char T[N], P[N];
int L[N], d[N];
int n, m;
void precalculare()
{
int i, k = 0;
L[0] = 0;
for ( i = 1; i < m; ++i )
{ if ( P[i] == P[k] ) k++;
else
{ while ( P[i] != P[k] && k > 0 )
k = L[k-1];
if ( P[i] == P[k] ) k++;
}
L[i] = k;
}
}
void KMP()
{
int i, k;
for ( i = 0; i < n; ++i )
{ if ( T[i] == P[k] ) k++;
else
{ while ( k > 0 && T[i] != P[k] )
k = L[k-1];
if ( T[i] == P[k] ) k++;
}
d[i] = k;
}
}
int main()
{ int i, ct = 0;
fin >> P >> T;
fin.close();
n = strlen(T);
m = strlen(P);
precalculare();
KMP();
for ( i = 0; i < n; ++i )
if ( d[i] == m )
ct++;
fout << ct << '\n';
for ( i = 0; i < n; ++i )
if ( d[i] == m )
fout << i - m + 1 << ' ';
fout.close();
return 0;
}