Pagini recente » Rating Deny Roman (denyroman) | Cod sursa (job #2713986)
/*
* Created by Andrei Arhire 01/03/2021
* Copyright © 2021 Andrei Arhire. All rights reserved.
* Expected verdict - Accepted
*/
#include <bits/stdc++.h>
#define pb push_back
#define zero(pos) pos&(-pos)
#define eb emplace_back
#define mp make_pair
using namespace std;
const long long NR = 3e5 + 1e2;
const long long oo = 1e16 ;
string s , t ;
vector < int > sol , P ( NR , 0 ) ;
ifstream in ("strmatch.in");
ofstream out ("strmatch.out");
signed main() {
ios::sync_with_stdio(false);
in.tie(nullptr);
in >> s >> t ;
int i , L = 0 ;
for ( i = 1 ; i < s.size() ; ++ i ) {
while ( L && s [ i ] != s [ L ] ) {
L = P [ L - 1 ] ;
}
if ( s [ i ] == s [ L ] ) {
++ L ;
}
P [ i ] = L ;
}
L = 0 ;
for ( i = 0 ; i < t.size() ; ++ i ) {
while ( L && t [ i ] != s [ L ] ) {
L = P [ L - 1 ] ;
}
if ( t [ i ] == s [ L ] ) {
++ L ;
}
if ( L == s.size() ) {
sol.pb(i+1-L);
L = P [ L - 1 ] ;
}
}
out << sol.size() << '\n' ;
for ( i = 0 ; i < min ( ( int ) sol.size() , 1000 ) ; ++ i ) {
out << sol [ i ] << ' ' ;
}
return 0;
}