Pagini recente » Cod sursa (job #706101) | Cod sursa (job #886309) | Cei mai harnici utilizatori infoarena | Cei mai harnici utilizatori infoarena | Cod sursa (job #1901576)
#include <bits/stdc++.h>
using namespace std;
fstream in ( "strmatch.in" , ios::in );
fstream out( "strmatch.out", ios::out );
const int DIM = 4e6 + 5;
vector<int> lst;
int z[DIM]; char str[DIM];
int main( void ) {
ios::sync_with_stdio( false );
in >> ( str + 1 ); int n = (int) strlen( str + 1 );
in >> ( str + n + 1 ); int m = (int) strlen( str + n + 1 );
int ans = 0; z[1] = n + m;
for( int k = 2, l = 1, r = 1; k <= n + m; k ++ ) {
if( k > r ) {
int i = 1;
while( str[i] == str[k + i - 1] && k + i - 1 <= n + m )
i ++;
z[k] = i - 1;
l = k;
r = k + z[k] - 1;
}
else {
int k2 = k - l + 1;
if( z[k2] < r - k + 1 )
z[k] = z[k2];
else {
int i = r - k + 1;
while( str[i] == str[k + i - 1] && k + i - 1 <= n + m )
i ++;
z[k] = i - 1;
l = k;
r = k + z[k] - 1;
}
}
if( z[k] >= n && k > n ) {
ans ++;
if( lst.size() < 1000 )
lst.push_back( k - n - 1 );
}
}
out << ans << endl;
for( int x : lst )
out << x << " ";
out << endl;
return 0;
}