Pagini recente » Borderou de evaluare (job #3322817) | Borderou de evaluare (job #1229426) | Borderou de evaluare (job #1481938) | Borderou de evaluare (job #2384688) | Cod sursa (job #3321055)
#include <bits/stdc++.h>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
const int nmax=2e6+5;
string s,t;
int lps[nmax];
void create_lps(int m)
{
int i=1, lg=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> rez;
void kmp(int n, int m)
{
int lg=0, i=1;
while ( i<n )
{
if ( t[i]==s[lg] )
{
lg++; i++;
if ( lg==m )
{
rez.push_back(i-m);
lg=lps[lg-1];
}
}
else if ( lg ) lg=lps[lg-1];
else i++;
}
}
int main()
{
f >> s >> t;
create_lps(s.size());
/*for (int i=0; i<s.size(); i++ )
cout << lps[i] << " ";*/
kmp(t.size(),s.size());
g << rez.size() << '\n';
for (int idx:rez )
g << idx << " ";
return 0;
}