Pagini recente » Profil Kayami | Cod sursa (job #857580) | Cod sursa (job #1528879) | Cod sursa (job #1230466) | Cod sursa (job #1804564)
#include <fstream>
#include <cstring>
const int NMAX = 2000000;
using namespace std;
ifstream cin ( "strmatch.in" );
ofstream cout ( "strmatch.out" );
char s[2*NMAX+5];
int pi[2*NMAX+5], sol[NMAX+5];
void kmp ( char* s, int *pi, int n ) {
int poz = 0;
for ( int i = 2; i <= n; i ++ ) {
while ( s[poz + 1] != s[i] && poz > 0 )
poz = pi[poz];
if ( s[i] == s[poz + 1] )
++poz;
pi[i] = poz;
}
}
int main() {
cin >> s + 1;
int n = strlen ( s + 1 );
s[n + 1] = '*';
cin >> s + n + 2;
int m = strlen ( s + 1 );
kmp ( s, pi, m );
int count = 0;
for ( int i = n + 2 ; i <= m ; ++ i )
if ( pi[i] == n )
++count;
cout << count << "\n";
count = 0;
for ( int i = n + 2 ; i <= m && count < 1000 ; ++ i )
if ( pi[i] == n ) {
cout << i - 2 * n - 1 << ' ';
++count;
}
cout << '\n';
return 0;
}