Pagini recente » Cod sursa (job #824834) | Cod sursa (job #2220091) | Cod sursa (job #1213611) | Cod sursa (job #2096980) | Cod sursa (job #2073587)
/*link: https://www.youtube.com/watch?v=0eaFFO1QlPA
tutorial romana https://www.youtube.com/watch?v=PbqZkoHO5SQ
*/
#include <iostream>
#include<fstream>
#include<cstring>
#define LUNG 2*1000*1000+1
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
int pi[LUNG],ap,ind[1001];
char p[LUNG],t[LUNG];
void prefix()
{
int m=strlen(p),q,k=0;
pi[0]=0;
k=0;
for(q=1; q<m; q++)
{
while(k>0&&p[k]!=p[q])
k=pi[k];
if(p[k]==p[q])
k++;
pi[q]=k;
}
}
void kmp()
{
int n=strlen(t),m=strlen(p),q=0,i;
prefix();
for(i=0; i<n; i++)
{
while(q>0&&p[q+1]!=t[i])
q=pi[q];
if(p[q+1]==t[i])
q++;
if(q==m-1)
{
ap++;
if(ap<=1000)
ind[ap]=i-m+1;
q=pi[q];
}
}
}
int main()
{
f.getline(p,sizeof(p));
f.getline(t,sizeof(t));
kmp();
g<<ap<<"\n";
for(int i=1;i<=min(1000,ap);++i)
g<<ind[i]<<" ";
return 0;
}