Pagini recente » Cod sursa (job #2950299) | Cod sursa (job #2337141) | Cod sursa (job #542053) | Cod sursa (job #423770) | Cod sursa (job #3237890)
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ifstream fin( "strmatch.in" );
ofstream fout( "strmatch.out" );
const int DIM = 2e6 + 1;
const int LIM = 1000;
int lps[DIM], fr;
vector<int> pos;
void get_lps( string s ) {
int n = s.length(), q = 0;
for ( int i = 1; i < n; ++i ) {
while ( q > 0 && s[q] != s[i] ) {
q = lps[q - 1];
}
if ( s[q] == s[i] ) ++q;
lps[i] = q;
}
}
void search_word( string s, string t ) {
int n = s.length(), m = t.length(), q = 0;
for ( int i = 0; i < m; ++i ) {
while ( q > 0 && s[q] != t[i] ) {
q = lps[q - 1];
}
if ( s[q] == t[i] ) ++q;
if ( q == n ) {
++fr;
if ( pos.size() < LIM ) {
pos.push_back(i - n + 1);
}
q = lps[q - 1];
}
}
}
int main() {
ios_base::sync_with_stdio(0);
fin.tie(0);
string s, t;
fin >> s >> t;
get_lps(s);
search_word(s, t);
fout << fr << "\n";
for ( auto x : pos ) fout << x << " ";
fin.close();
fout.close();
return 0;
}