Pagini recente » Cod sursa (job #448158) | Cod sursa (job #1237157) | Cod sursa (job #1133131) | Cod sursa (job #708431) | Cod sursa (job #2886489)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
const int NMAX=2000005;
int N, M, total;
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){
total++;
if(total<=1000)
sol.push_back(i-j);
j=lps[j-1];
}
}
}
///O(N+M)
int main()
{
fin>>A>>B;
N=A.size();
M=B.size();
KMP();
fout<<total<<'\n';
for(auto x: sol)
fout<<x<<' ';
fin.close();
fout.close();
return 0;
}