Pagini recente » Cod sursa (job #2157599) | Cod sursa (job #1042973) | Cod sursa (job #994815) | Cod sursa (job #1165151) | Cod sursa (job #1311306)
//KMP by andreimdv https://www.youtube.com/watch?v=kBW6oPaVjq0
#include <fstream>
#include<cstring>
#include<vector>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char s[2000010],t[2000010];
int n,i,m,nr,p[2000010];
int k,q,snr;
vector<int> v;
vector<int> ::iterator it;
int main()
{
fin>>(t+1)>>(s+1);
//compute-prefix-function
m=strlen(t+1);
k=0;
for(i=2;i<=m;++i) //parcurgem sirul t pentru a gasi prefixele din acesta: ex ABCdefABdcABC
{
while(k>0 && t[k+1]!=t[i]) //prefixul nu mai continua
k=p[k];
if(t[k+1]==t[i]) //prefixul se prelungeste
k=k+1;
p[i]=k; //vectorul p retine lungimea prefixului pentru fiecare pozitie
}
//************************
q=0; // numarul de caractere care sunt la fel
n=strlen(s+1);
for(i=1;i<=n;++i)
{
while(q>0&& t[q+1]!=s[i])
q=p[q];
if(t[q+1]==s[i])//urmatorul caracter este la fel
q=q+1;
if(q==m)
{
nr++;
v.push_back(i-m);
q=p[q];// folosind vectorul constrit cu ajutorul functiei de precomputare a prefixelor, in loc sa parcurgem integral textul sarim la urmatorul loc in care se poate afla sirul cautat
}
}
fout<<nr<<'\n';
i=0;
for(it=v.begin();it!=v.end();it++)
{
i++;
fout<<*it<<" ";
if(i==1000)
return 0;
}
return 0;
}