Pagini recente » Cod sursa (job #910707) | Cod sursa (job #1008838) | Cod sursa (job #735791) | Cod sursa (job #324072) | Cod sursa (job #1866286)
//kmp
#include <iostream>
#include <vector>
#include <fstream>
#include <cmath>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
string a,b;
int fa[2000010];
void calcSufInf(int n){
int j=0;
fa[j] = 0;
for(int i=1;i<a.size();){
if(a[i] == a[j]){
fa[i] = j+1;
i++;
j++;
}
else {
bool aux = false;
while(j!=0){
if(a[i]!=a[j]){
j = fa[j-1];
}
else {
fa[i] = j+1;
i++;
j++;
aux = true;
}
}
if(aux == false)
i++;
}
}
}
int main()
{
vector<int>rez;
fin>>a>>b;
calcSufInf(a.size());
/*for(int i=0;i<a.size();i++)
fout<<fa[i]<<' ';*/
int j=0;
for(int i=0;i<b.size();){
if(b[i] == a[j]){
i++;
j++;
}
else {
j=fa[j-1];
}
if(j==0 && (a[j]!=b[i]))
i++;
if(j==a.size()-1 && a[j] == b[i])
rez.push_back(i-a.size()+1);
}
fout<<rez.size()<<'\n';
for(int i=0;i<rez.size();i++){
if(i<=999)
fout<<rez[i]<<' ';
else break;
}
return 0;
}