Pagini recente » Cod sursa (job #270784) | Borderou de evaluare (job #2860293) | Cod sursa (job #2847119)
#include <bits/stdc++.h>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
const int SIZE = 25;
char s1[SIZE],s2[SIZE];
int n,m,v[SIZE],cnt,sol[SIZE];
void pattern()
{
int i,j=1;
for(i=2;i<=n;i++)
{
if(s1[i]==s1[j])
{
v[i]=v[i-1]+1;
j++;
}
else
{
v[i]=0;
j=1;
}
}
//for(i=1;i<=n;i++)g<<v[i]<<' ';
}
void kmp()
{
int i,j=0;
for(i=1;i<=m;i++)
{
if(cnt==3)
{
cnt++;
cnt--;
}
if(s2[i]==s1[j+1])
{
j++;
if(j==n)
{
cnt++;
sol[cnt]=i-n;
j=v[j];
}
}
else
{
j=1;
}
}
g<<cnt<<'\n';
for(i=1;i<=cnt;i++)g<<sol[i]<<' ';
}
int main()
{
s1[0]=' ';
s2[0]=' ';
f.getline(s1+1,SIZE);
f.getline(s2+1,SIZE);
n=strlen(s1)-1;
m=strlen(s2)-1;
pattern();
kmp();
return 0;
}