Pagini recente » Cod sursa (job #1731357) | Cod sursa (job #1373518) | Cod sursa (job #2224776) | Cod sursa (job #2390546) | Cod sursa (job #2714279)
/*
* 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 = 2e6 + 1e2;
const long long oo = 1e16;
string s , t ;
int p [ NR ];
int cnt ;
int sol [ NR ] ;
ifstream in ( "strmatch.in" ) ;
ofstream out ( "strmatch.out" ) ;
signed main() {
ios::sync_with_stdio(false);
in.tie(nullptr);
in >> s >> t ;
int L = 0 ;
for ( int i = 1 ; i < s.size() ; ++ i ) {
while ( L != 0 && s [ L ] != s [ i ] ) { //lungimea maxima a unei secvente
L = p [ L - 1 ] ; // din S care se termina in i si totodata incepe in S
}
if ( s [ i ] == s [ L ] ) {
++ L ;
}
p [ i ] = L ;
}
L = 0 ;
for ( int i = 0 ; i < t.size() ; ++ i ) { // lungimea maxima a unei secvente
while ( L != 0 && s [ L ] != t [ i ] ) { // din T se termina in i si incepe in S
L = p [ L - 1 ] ;
}
if ( t [ i ] == s [ L ] ) {
L ++ ;
}
if ( L == s.size() ) {
sol [ ++ cnt ] = i - s.size() + 1 ;
L = p [ L - 1 ] ;
}
}
out << cnt << '\n' ;
for ( int i = 1 ; i <= min ( 1000 , cnt ) ; ++ i ) {
out << sol [ i ] << ' ' ;
}
return 0;
}