Pagini recente » Istoria paginii runda/20052020 | Cod sursa (job #2351240) | Cod sursa (job #1068845) | Cod sursa (job #2221030) | Cod sursa (job #1830928)
#include <iostream>
#include <cstdio>
#include <string>
using namespace std;
string text,patern;
int sir[20000000],nr=0,x=0,a[100];
void citire()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
getline(cin,patern);
getline(cin,text);
}
void patern_making()
{
int n=patern.length();
int j=0;
for(int i=1; i<n; i++)
{
if(patern[i]==patern[j])
{
sir[i]=j+1;
j++;
}
else
{
j--;
while(j>=0)
{
j=sir[j];
if(patern[i]==patern[j])
{
sir[i]=j+1;
j++;
break;
}
else
j--;
}
if(j<0)
{
sir[i]=0;
j=0;
}
}
}
}
void cautare()
{
int j=0,v=0;
int n=patern.length();
int m = text.length();
for(int i=0; i<m; i++)
{
if(text[i]==patern[j])
j++;
else if(j)
j=sir[j-1];
if(j==n)
{
nr++;
j = sir[j - 1];
a[x++]=i-n+1;
}
}
}
int main()
{
citire();
patern_making();
cautare();
int n=patern.length();
cout<<nr<<endl;
if(x>1000)
for(int i=0;i<1000;i++)
cout<<a[i]<<" ";
else
for(int i=0;i<x;i++)
cout<<a[i]<<" ";
return 0;
}