Pagini recente » Cod sursa (job #1379552) | Cod sursa (job #1635142) | Cod sursa (job #2127149) | Cod sursa (job #2436020) | Cod sursa (job #2949295)
#include <fstream>
using namespace std;
const int nmax = 2e6;
int pi[2 * nmax + 1];
ifstream fin ( "strmatch.in" );
ofstream fout ( "strmatch.out" );
int main() {
string s, s2;
int n, m;
fin >> s >> s2;
n = s.size ();
m = s2.size ();
s = s + '#' + s2;
pi[0] = 0;
for ( int i = 1; i < n + 1 + m; i++ ) {
int j = pi[i - 1];
while ( j > 0 && s[i] != s[j] )
j = pi[j - 1];
if ( s[i] == s[j] )
j++;
pi[i] = j;
}
int cnt = 0;
for ( int i = n + 1; i < n + 1 + m; i++ )
if ( pi[i] == n )
cnt++;
fout << cnt << '\n';
cnt = 0;
for ( int i = n + 1; i < n + 1 + m; i++ )
if ( pi[i] == n && cnt < 1000 ) {
fout << ( i - ( n + 1 ) ) - n + 1 << ' ';
cnt++;
}
return 0;
}