シーケンス列アルゴリズム2
793 ワード
問題説明:文字列S 1と同じ文字列の最初の開始位置を、列S中のindex番目の文字から求める.
アルゴリズム構想:index番目の文字からシリアルSをスキャンし、その要素値がS 1の最初の文字と等しい場合、S 1が終了するまで、その後の要素値が順次同じか否かを判定する.同じであれば戻り、そうでなければSスキャンが完了するまで上記の手順を続行します.
アルゴリズム構想:index番目の文字からシリアルSをスキャンし、その要素値がS 1の最初の文字と等しい場合、S 1が終了するまで、その後の要素値が順次同じか否かを判定する.同じであれば戻り、そうでなければSスキャンが完了するまで上記の手順を続行します.
// 1
int part(SqString &S,SqString &S1,int index)
{
int i=index,j=0;
while(i<S.length&&j<S1.length)
{
if(S.data[i]==S1.data[j])
{
i++;
j++;
}
else
{
i=i-j+1;
j=0;
}
}
if(j>=S1.length)
return (i-S1.length);
else
return -1;
}
// 2
int Part(SqString S,SqString S1,int index)
{
int i,j,k;
int n=S.length;
int m=S1.length;
for(i=index;i<n-m;i++)
{
for(j=0,k=i;j<m&&S1.data[j]==S.data[k];j++,k++);
if(j==m)
return i;
}
return -1;
}