Pagini recente » Cod sursa (job #460538) | Cod sursa (job #488295) | Cod sursa (job #3192507) | Cod sursa (job #41352) | Cod sursa (job #2834675)
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
using namespace std;
const int LEN_MAX = 2e6;
const char BORD = '$';
const int LIMIT = 1e3;
const int STOP = 0;
int lps[1 + LEN_MAX];
void process_lps ( string text ) {
int n = text.size ();
lps[0] = STOP;
for ( int i = 1; i < n; i ++ ) {
int prev = lps[i - 1];
while ( prev != STOP && text[i] != text[prev] )
prev = lps[prev - 1];
///cout << prev << " ";
if ( text[i] == text[prev] )
lps[i] = prev + 1;
else
lps[i] = 0;
}
}
/// ABA$CABBCABABAB
ifstream fin ( "strmatch.in" );
ofstream fout ( "strmatch.out" );
int main()
{
string pattern, text;
fin >> pattern >> text;
int target = pattern.size ();
pattern += BORD; pattern += text;
int total = pattern.size ();
process_lps ( pattern );
vector<int> ans;
for ( int i = target; i < total && (int) ans.size () < LIMIT; i ++ )
if ( lps[i] == target )
ans.push_back ( i );
fout << ans.size () << "\n";
for ( auto pos : ans )
fout << pos - 2 * target << " ";
return 0;
}