Pagini recente » Borderou de evaluare (job #2053359) | Borderou de evaluare (job #1438041) | Borderou de evaluare (job #394080) | Cod sursa (job #292125) | Cod sursa (job #2306015)
#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
#define NMAX 2000000
#define END 1000
using namespace std;
string a, b;
vector <int> ans;
int pi[1 + NMAX];
int main() {
freopen ( "strmatch.in", "r", stdin );
freopen ( "strmatch.out", "w", stdout );
int p;
cin >> a >> b;
int k = 0;
for ( int i = 1; i < a.size(); i++ ) {
while ( k > 0 && a[k] != a[i] )
k = pi[k - 1];
if ( a[k] == a[i] )
k++;
pi[i] = k;
}
k = 0;
for ( int i = 0; i < b.size(); i++ ) {
while ( k > 0 && a[k] != b[i] )
k = pi[k - 1];
if ( a[k] == b[i] )
k++;
if ( k == a.size() ) {
if ( ans.size() < END )
ans.push_back ( i - a.size() + 1 );
else
ans.push_back ( -1 );
}
}
cout << ans.size() << endl;
for ( vector<int>::iterator it = ans.begin(); it != ans.end() && *it != -1; it++ )
cout << *it << ' ';
return 0;
}