Pagini recente » Cod sursa (job #2014356) | Cod sursa (job #1519232) | Cod sursa (job #2841614) | Cod sursa (job #901322) | Cod sursa (job #1045914)
#include<iostream>
#include<fstream>
#include<string.h>
using namespace std;
char s1[2000001],s2[2000001];
int pi[2000001],poz[1001];
void citire()
{
ifstream f("strmatch.in");
f>>s1;
f.get();
f>>s2;
f.close();
}
void prefix()
{
int n=strlen(s1)-1;
pi[1]=0;
int k=0;
for(int i=1;i<=n;i++)
{
while((k>0)&&(s1[k+1]!=s1[i]))k=pi[k];
if(s1[k+1]=s1[i])
k=k+1;
pi[i]=k;
}
}
int subsiruri()
{
int i,n=0,k=0;
prefix();
for(i=0;i<strlen(s2);i++)
{
while((k>=0)&&(s1[k+1]!=s2[i]))k=pi[k];
if(s1[k+1]==s2[i])k++;
if(k==strlen(s1)-1)
{
k=pi[k];
n++;
if(n<=1000)poz[n]=i-strlen(s1)+1;
}
}
return n;
}
void afisare(int n)
{
ofstream g("strmatch.out");
g<<n<<endl;
for(int i=1;i<=n;i++)
g<<poz[i]<<" ";
}
int main()
{
citire();
int n=subsiruri();
afisare(n);
return 0;
}