Pagini recente » Cod sursa (job #40674) | Cod sursa (job #2466647) | Cod sursa (job #2860165) | Cod sursa (job #447848) | Cod sursa (job #3237926)
#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 lcp[DIM];
void get_lcp( string s ) {
int n = s.length(), l = 0, r = 0;
for ( int i = 1; i < n; ++i ) {
if ( i < r ) {
lcp[i] = min(lcp[i - l], r - i);
}
while ( i + lcp[i] < n && s[lcp[i]] == s[i + lcp[i]] ) {
++lcp[i];
}
if ( i + lcp[i] - 1 >= r ) {
l = i;
r = i + lcp[i] - 1;
}
}
}
int main() {
ios_base::sync_with_stdio(0);
fin.tie(0);
string s, t;
fin >> s >> t;
t = s + '#' + t;
get_lcp(t);
vector<int> sol;
int fr = 0;
for ( int i = s.length() + 1; i < (int)t.length(); ++i ) {
if ( lcp[i] == (int)s.length() ) {
++fr;
if ( sol.size() < LIM ) sol.push_back(i - s.length() - 1);
}
}
fout << fr << "\n";
for ( auto i : sol ) fout << i << " ";
fin.close();
fout.close();
return 0;
}