Pagini recente » Cod sursa (job #2420806) | Cod sursa (job #2643032) | Cod sursa (job #662347) | Cod sursa (job #267755) | Cod sursa (job #2809053)
#include <iostream>
#include <vector>
#include <fstream>
using namespace std;
const int NMAX = 2e6;
int z[2 * NMAX + 1];
ifstream fin( "strmatch.in" );
ofstream fout( "strmatch.out" );
void calculate_z( const string& s ) {
int i, l, r, n = s.size();
l = r = 0;
for ( i = 1; i < n; i ++ ) {
if ( r < i ) {
l = r = i;
while ( r < n && s[r - l] == s[r] )
r ++;
z[i] = r - l;
r --;
} else {
int aux = i - l;
if ( z[aux] <= r - i )
z[i] = z[aux];
else {
l = i;
while ( r < n && s[r] == s[r - l] )
r ++;
z[i] = r - l;
r --;
}
}
}
}
vector <int> ans;
void solve() {
int cnt = 0;
string s1, s2;
fin >> s1 >> s2;
s2 = s1 + '#' + s2;
calculate_z( s2 );
for ( int i = s1.size(); i < s2.size(); i ++ ) {
if ( z[i] == s1.size() ) {
cnt ++;
if ( ans.size() < 1000 )
ans.push_back( i );
}
}
fout << cnt << '\n';
for ( int i = 0; i < ans.size(); i ++ )
fout << ans[i] - s1.size() - 1 << ' ';
}
int main() {
solve();
return 0;
}