Pagini recente » Cod sursa (job #1979334) | Cod sursa (job #1045438) | Cod sursa (job #3224721) | Cod sursa (job #1665977) | Cod sursa (job #1498736)
#include <iostream>
#include <fstream>
#include <string.h>
#include <vector>
#include <stdio.h>
using namespace std;
char text[10000],ss[1000];
int P[1000];
void citire()
{
ifstream fin("strmatch.in");
fin.getline(ss,1000);
fin.getline(text,10000);
}
void prefix()
{
int a=0;
for(int i=1;i<strlen(ss);i++)
{
while(a && ss[a+1]!=ss[i])
a=P[a];
if(ss[i]==ss[a])
a++;
P[i]=a;
}
}
vector <int> sol;
int cont;
void cautare()
{
int n=strlen(ss),m=strlen(text),k=0,i=0,j=0;
while(m-k>=n)
{
while(j<=n && ss[j]==text[i])
i++,j++;
if(j>=n)
{
cont++;
sol.push_back(k);
}
if(P[j-1]>0)
k=i-P[j-1];
else
{
if(i==k)
i++;
k=i;
}
if(j>0)
j=P[j-1];
}
freopen("strmatch.out","w",stdout);
printf("%d\n",cont);
for(int i=0;i<cont;i++)
printf("%d ",sol[i]);
}
int main()
{
citire();
prefix();
cautare();
return 0;
}