シーケンス列アルゴリズム2

793 ワード

問題説明:文字列S 1と同じ文字列の最初の開始位置を、列S中のindex番目の文字から求める.
アルゴリズム構想: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;

}