Pagini recente » Cod sursa (job #491025) | Cod sursa (job #1637640) | Cod sursa (job #2333946) | Cod sursa (job #406239) | Cod sursa (job #2892692)
#include <bits/stdc++.h>
#define MAX_N 2000000
#define MAX_SOL 1000
using namespace std;
int z[2 * MAX_N + 1];
vector <int> ans;
int main() {
ifstream cin( "strmatch.in" );
ofstream cout( "strmatch.out" );
int l, r, i;
string s, pat, text;
cin >> pat >> text;
s = pat + '#' + text;
z[0] = 0;
l = r = 0;
for ( i = 1; i < s.size(); i++ ) {
if ( i <= r )
z[i] = max( r - i + 1, z[i - l] );
while ( i + z[i] < s.size() && s[z[i]] == s[i + z[i]] )
z[i]++;
if ( i + z[i] - 1 > r ) {
l = i;
r = i + z[i] - 1;
}
}
for ( i = 0; i < s.size(); i++ ) {
if ( z[i] == pat.size() )
ans.push_back( i - pat.size() - 1 );
}
cout << ans.size() << "\n";
for ( i = 0; i < ans.size() && i < MAX_SOL; i++ )
cout << ans[i] << " ";
return 0;
}