Pagini recente » Cod sursa (job #3210778) | Cod sursa (job #3249159) | Cod sursa (job #2704655) | Cod sursa (job #3280750) | Cod sursa (job #2742888)
#include <fstream>
#include <vector>
#include <cstring>
using namespace std;
ifstream fin( "strmatch.in" );
ofstream fout( "strmatch.out" );
const int MAXL = 2000002;
const int MAX_OUT = 1000;
char t[MAXL], w[MAXL];
int n, m;
int pi[MAXL];
vector<int> sol;
void precalc() {
int q = 0;
for ( int i = 2; i <= m; ++i ) {
while ( q > 0 && w[q] != w[i - 1] ) {
q = pi[q];
}
if ( w[q] == w[i - 1] ) {
++q;
}
pi[i] = q;
}
}
int main() {
int q = 0, cnt = 0;
fin >> w >> t;
n = strlen( t );
m = strlen( w );
precalc();
for ( int i = 1; i <= n; ++i ) {
while ( q > 0 && w[q] != t[i - 1] ) {
q = pi[q];
}
if ( w[q] == t[i - 1] ) {
++q;
}
if ( q == m ) {
if ( sol.size() < MAX_OUT ) {
sol.push_back( i );
}
++cnt;
}
}
fout << cnt << "\n";
for ( int i = 0; i < (int)sol.size(); ++i ) {
fout << sol[i] - m << " ";
}
fin.close();
fout.close();
return 0;
}