Pagini recente » Monitorul de evaluare | Monitorul de evaluare | Cod sursa (job #3322288) | Cod sursa (job #472745) | Cod sursa (job #3321090)
#include <bits/stdc++.h>
using namespace std;
ifstream fin ( "strmatch.in" ) ;
ofstream fout ( "strmatch.out" ) ;
unordered_map<int,int>lps;
void llps ( string s )
{
int i = 1 , m = s.size() , lg = 0 ;
lps[0] = 0;
while ( i < m )
{
if ( s[i] == s[lg] )
{
++lg;
lps[i]=lg;
++i;
}
else if ( lg )
lg = lps[lg-1];
else
lps[i] = 0 , ++i ;
}
}
vector<int>ans;
int nr = 0 ;
void idiot ( string s , string t )
{
int i = 0 , lg = 0 , n = s.size() , m = t.size() ;
while ( i < n )
{
if ( s[i] == t[lg] )
{
++lg;
++i;
if (lg==m)
{
ans.push_back(i-lg);
lg=lps[lg-1];
}
}
else if ( lg )
lg = lps[lg-1];
else
++ i ;
}
}
signed main()
{
string s;
fin >> s ;
string t ;
fin >> t ;
llps(s);
idiot(t,s);
fout << ans.size() << '\n';
int nr = 0 ;
for ( auto it : ans )
{
++nr;
if ( nr == 1001 )
break;
fout << it << ' ' ;
}
return 0;
}