Pagini recente » Cod sursa (job #1981983) | Cod sursa (job #1446632) | Cod sursa (job #2274031) | Cod sursa (job #751140) | Cod sursa (job #3236461)
#include <bits/stdc++.h>
#include <fstream>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int o, vct[2000005];
void calclps(char* pat, int m, int* lps);
void kmp(char* pat, char* txt)
{
int m=strlen(pat);
int n=strlen(txt);
int lps[m];
calclps(pat, m, lps);
int i=0;
int j=0;
while((n-i)>=(m-j))
{
if(pat[j]==txt[i])
{
i++;
j++;
}
if(j==m)
{
o++;
vct[o]=i-j;
j=lps[j-1];
if(o==1000) return 0;
}
else if(i<n && pat[j]!=txt[i])
{
if(j!=0)
{
j=lps[j-1];
}
else i++;
}
}
}
void calclps(char* pat, int m, int* lps)
{
int len=0;
lps[0]=0;
int i=1;
while(i<m)
{
if(pat[i]==pat[len])
{
len++;
lps[i]=len;
i++;
}
else
{
if(len!=0)
{
len=lps[len-1];
}
else
{
lps[i]=0;
i++;
}
}
}
}
char txt[2000005], pat[2000005];
int main()
{
fin>>pat;
fin>>txt;
kmp(pat, txt);
fout<<o<<'\n';
for(int i=1; i<=o; i++)
fout<<vct[i]<<' ';
return 0;
}