Pagini recente » Cod sursa (job #1552938) | Cod sursa (job #665067) | Cod sursa (job #2023553) | Monitorul de evaluare | Cod sursa (job #2829648)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
const int NMAX=2000005;
int N, M;
string A, B;
int lps[NMAX];
vector<int> sol;
/// lps[i]=prefixul maxim al subsecventei [0,...,i] care
/// este de asemenea si sufix al aceleasi subsecvente
void computeLPS()
{
/// lungimea anteriorului prefix maxim care e si sufix
int len=0;
lps[0]=0;
int i=1;
while(i<N){
if(A[i]==A[len]){
lps[i]=len+1;
len++;
i++;
}
else{
if(len!=0)
len=lps[len-1];
else{
lps[i]=0;
i++;
}
}
}
}
void KMP()
{
computeLPS();
int i=0, j=0;
if(N>M)
return;
while(i<M){
if(B[i]==A[j]){
i++;
j++;
}
else{
if(j!=0)
j=lps[j-1];
else
i++;
}
if(j==N)
sol.push_back(i-j);
}
}
/// O(N+M)
int main()
{
fin>>A>>B;
N=A.size();
M=B.size();
KMP();
fout<<sol.size()<<'\n';
for(auto x: sol)
fout<<x<<' ';
fin.close();
fout.close();
return 0;
}