Pagini recente » Cod sursa (job #2657091) | Cod sursa (job #2191922) | Cod sursa (job #1613486) | Cod sursa (job #878125) | Cod sursa (job #2748955)
#include <bits/stdc++.h>
#define NMAX 1009
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char a[NMAX];
char b[NMAX];
int poza[NMAX];
int pozb[NMAX];
int lga,lgb;
vector<int> sol;
void pre()
{
poza[0]=-1;
int j=-1;
int i;
for(i=1;i<lga;i++)
{
while(j>=0 && a[j+1]!=a[i])
j=poza[j];
if(a[i]==a[j+1]) ///poate nu gasesc nimic
j++;
poza[i]=j;
}
}
void kmp()
{
int i,j;
j=-1;
for(i=0;i<lgb;i++)
{
while( b[i]!= a[j+1] && j>=0)
j= poza[j];
if( b[i]== a[j+1])
j++;
pozb[i]=j;
if(j==lga-1)
sol.push_back(i-lga+1);
}
}
int main()
{
fin>>a>>b;
int i;
lga=strlen(a);
lgb=strlen(b);
pre();
kmp();
fout<<sol.size()<<'\n';
for(i=0;i< sol.size() && i< 1000;i++ )
fout<< sol[i]<<" ";
}