Pagini recente » Cod sursa (job #1979694) | Cod sursa (job #818659) | Cod sursa (job #2070279) | Cod sursa (job #1191589) | Cod sursa (job #2809051)
#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() {
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() && ans.size() < 1000 )
ans.push_back( i );
}
fout << ans.size() << '\n';
for ( int i = 0; i < ans.size(); i ++ )
fout << ans[i] - s1.size() - 1 << ' ';
}
int main() {
solve();
return 0;
}