Pagini recente » Cod sursa (job #2041529) | Cod sursa (job #2478270) | Cod sursa (job #325922) | Cod sursa (job #3283593) | Cod sursa (job #2432861)
#include <fstream>
#include <cstring>
using namespace std;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
int k;
void creare_lps(char a[],int m,int lps[])
{
int i=1,len;
lps[0]=len=0;
while (i<m)
{
if (a[i]==a[len])
{
len++;
lps[i]=len;
i++;
}
else
{
if (len!=0)
{
len=lps[len-1];
}
else
{
lps[i]=0;
i++;
}
}
}
}
void kmp(char a[],int m,char b[],int n,int lps[],int poz[])
{
int i=0,j=0;
while (i<n)
{
if (b[i]==a[j])
{
i++;
j++;
if (j==m)
{
poz[k++]=i-m;
if (k>999) break;
j=lps[j-1];
}
}
else
{
if (j!=0) j=lps[j-1];
else i++;
}
}
}
int main()
{
char a[2000005],b[2000005];
int lps[2000005],poz[1005];
cin.getline(a,2000005);
cin.getline(b,2000005);
int m=strlen(a),n=strlen(b);
creare_lps(a,m,lps);
kmp(a,m,b,n,lps,poz);
cout << k << '\n';
for (int i=0;i<k;i++)
{
cout << poz[i] << " ";
}
}