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