C＃によるアルゴリズムとデータ構造

８．文字列処理
８．１Ｃ＃の文字列
Ｃ＃では， “ABCD”のように文字列を２重引用符で挟んで指定
します。ASCIIコード体系のとき，以下のような内部形式となり
ます。
0 1 0 0 0 0 0 1
文字 ‘A’
0
0
文字 ‘B’
0 1 0 0 0 0 1 1
文字 ‘C’
0
1
0
0
0
1
0
0
文字 ‘D’
0
0
0
0
0
0
0
0
ナル文字
‘\0’
ナル文字
A B C D \0
1
0
0
0
0
1
文字列の内部形式を
listBox1に表示するプログラム
文字列の内部表現
private string binaryScaleString(long V)
{
long VV=V;string S="";
for(int i=0;i<16;i++, VV /=2 )
S = ((VV % 2 ==0) ? "0" : "1") + S;
return S;
}
private void strDump(string S)
{
listBox1.Items.Clear();
for(int i=0;i<S.Length;i++)
{
long V=(long)S[i];
string X = V.ToString("X");
string B = binaryScaleString(V);
if(X.Length==2) X = " " + X;
listBox1.Items.Add(S[i].ToString() + "\t" + X + "\t" + B);
}
}
文字列の内部表現 Clickイベントハンドラ実行結果
private void button1_Click(object sender, System.EventArgs e)
{
strDump("文字列string");
}
配列による文字列
文字リテラルは，本来，
その内容を自由に書き換えて使うものではありません。
ですから，C#では，stringはRead Only とみなされており，
陽に代入は許されません．
自由に入れ替える処理を記述するためには，
次のようにchar型の配列として宣言します。
なお，char型配列をstringとして扱うには，
以下の例のようにCharToString関数を使います（C, C++との違い）。
private void button2_Click(object sender, System.EventArgs e)
{
char[] CH =new char[10];
CH[0]='文';CH[1]='字';CH[2]='列';
CH[3]='s' ;CH[4]='t' ;CH[5]='r' ;
CH[6]=’i' ;CH[7]='n' ;CH[8]='g';CH[9]='\0';
strDump(CharToString(CH));
}
８．２文字列の基本操作
（１）文字列の長さ
文字列の最後はナル文字です。
ですから，ナル文字を検索することで
文字列の長さを求めることができます。。
ナル文字
A B C D \0
private int str_len(char[] ch)
{
int i=0;
while(ch[i] != '\0')i++;
return i;
}
配列の大きさと文字列の長さ
文字列を格納するための配列のサイズと
文字列の長さは必ずしも一致しません。
配列の大きさと文字列の長さの違いを
以下のプログラムで確認してみましょう。
（C++,C の strlen 関数は，次のように，文字列.Lengthと書きます）
private void button3_Click(object sender, System.EventArgs e)
{
char[] CH =new char[12];
CH[0]='文';CH[1]='字';CH[2]='列';
CH[3]='s' ;CH[4]='t' ;CH[5]='r' ;
CH[6]='i'; CH[7]='n' ;CH[8]='g';CH[9]='\0';
MessageBox.Show(CH.Length.ToString());
// 配列のサイズ=12
MessageBox.Show(str_len(CH).ToString()); // 文字列の長さ=9
MessageBox.Show(CharToString(CH).Length.ToString());
// 文字列の長さ=9
}
（２）文字列からの文字の探索
文字列から任意の文字を探索する手続きは次のようになります。
private int 文字探索(string X, char C)
{
int i=0;
while (i < X.Length && X[i] !=C)i++;
if(i < X.Length) return i;
return -1;
}
文字探索のメソッド（Ｃのｓｔｒｃｈｒ，ｓｔｒｒｃｈｒに相当）
(a) String．IndexOf
特定の文字が文字列内で最初に出現する位置を返却。先頭は0，指定した文字が見
つからない場合，–1 を返す。大文字と小文字は区別される。
string S = ”Peter Piper picked a peck";
MessageBox.Show(S.IndexOf(’p'));
この例では8 と表示される。
（ｂ）String.LastIndexOf
指定した文字列が文字列内で最後に出現する位置を返却。先頭は0，指定した文字
が見つからない場合，-1を返す。大文字と小文字は区別される。
string S = ”Peter Piper picked a peck";
MessageBox.Show(S.LastIndexOf(’p'));
この例では21 と表示される。
文字列S1,S2を比較し，
（３）文字列の比較
S1が大きければ正の整数値，
小さければ負の整数値，
等しければ0を返却する関数の処理を以下に示します。
private int str_cmp(string S1, string S2)
{
int i=0;
while(i<S1.Length && i<S2.Length && S1[i]==S2[i]) i++;
if
(i== S1.Length && i== S2.Length) return 0;
else if(I < S1.Length && I < S2.Length)
return ((int)S1[i]-(int)S2[i]);
else if(i<S1.Length) return 1;
else return -1;
}
private void button5_Click(object sender, System.EventArgs e)
{
string S1
= textBox1.Text;
string S2
= textBox2.Text;
MessageBox.Show(str_cmp(S1,S2).ToString());
}
Ｃ＃の文字列比較メソッド
文字列比較のメソッドは用意されていますので，
通常は，わざわざプログラムを作る必要はありません。
たとえば，String.Compare メソッドでは，
2 つの文字列を比較します。
このメソッドでは，以下の結果を返却します。
(a) 引数１が引数２より大きいとき，正の整数
(b) 引数１が引数２より小さいとき，負の整数
(c) 引数１と引数２が等しいとき０
この他，CompareOrdinal ，CompareTo，Equals，StartsWith ， EndsWith
などがあります。詳しくはＣ＃のマニュアルやヘルプを参照してください。
８．３文字列探索
（１）文字列探索とは
文字列探索（string searching）とは，
ある文字列の中に，別の文字列が含まれているかどうか，
含まれている場合は，その位置を示すこと。
探索される側の文字列：テキスト（text）
探し出すための文字列：パターン（pattern）
（２）力まかせ法（単純法，素朴法）
力まかせ法（brute forth method）の手順
(a)
(b)
(c)
0
P
1
E
2
T
3
E
4
R
P
I
P
\0
３文字目が一致しない
0
P
1
E
2
T
3
E
4
R
P
I
P
\0
1
E
2
T
3
E
4
R
5
P
P
I
P
\0
0
P
5
P
5
P
6
I
6
I
7
P
7
P
8
E
9
R
10
\0
8
E
9
R
10
\0
9
R
10
\0
１文字目が一致しない
6
I
7
P
8
E
１文字目が一致しない
力まかせ法の手順２
力まかせ法（brute forth method）の手順
(d)
(e)
(f)
0
P
0
P
0
P
1
E
1
E
1
E
2
T
2
T
2
T
3
E
4
R
5
P
6
I
P
I
P
\0
3
E
4
R
5
P
6
I
7
P
P
I
P
\0
4
R
5
P
6
I
7
P
8
E
P
I
P
\0
3
E
7
P
8
E
9
R
10
\0
１文字目が一致しない
8
E
9
R
10
\0
１文字目が一致しない
9
R
10
\0
全文字一致
力まかせ法のプログラム
private int 力まかせ法(string 文字列, string パターン)
{
int P1=0; int P2=0;
while(P1<文字列.Length && P2<パターン.Length)
{
if(文字列[P1] == パターン[P2]){ P1++; P2++;}
else
{ P1 = P1 - P2 + 1; P2 = 0; }
}
if(P2==パターン.Length) return(P1 - P2);
return -1;
}
private void button2_Click(object sender, System.EventArgs e)
{
string 文字列
= textBox1.Text;
string パターン = textBox2.Text;
label5.Text=力まかせ法(文字列, パターン).ToString();
}
（３）ＫＭＰ法
力まかせ法では，不一致文字があると，
パターンを移動して再びパターンの先頭から照合する。
それまでの照合結果が捨てられる。
パターンの特徴を活かし，そこまでの照合結果を有効活用する
D. E. KnuthとV. R. Pratt，J. H. Morris が
ほぼ同時期に考案した方法。
Knuth-Pratt-Morris 法，略してＫＭＰ法と呼ばれる。
KMP法の考え方
［例］パターン移動の際，何文字目から照合を再開するかを事前に決めておく。
(a)
(b)
(c)
0
P
1
S
2
E
3
A
4
S
5
E
6
R
7
P
S
E
A
S
E
R
\0
1文字目が一致しない
0
P
1
S
2
E
3
A
4
S
5
E
6
D
7
P
8
E
S
E
A
S
E
R
\0
6文字目が一致しない
1
S
2
E
3
A
4
S
5
E
6
R
7
P
8
E
9
R
10
\0
S
E
A
S
E
R
\0
0
P
（３文字目から照合）
8
E
9
R
9
R
10
\0
10
\0
照合再開位置（１）
(a) １文字目で不一致
0
P
1
?
2
?
3
?
4
?
5
?
6
?
S
E
A
S
E
R
\0
7
?
8
?
9
?
10
?
1文字目が一致しない
1文字目から照合を開始
0
P
1
?
2
?
3
?
4
?
5
?
6
?
7
?
S
E
A
S
E
R
\0
8
?
9
?
10
?
照合再開位置（２）
(b) ２文字目で不一致
0
S
1
X
2
?
3
?
4
?
5
?
6
?
S
E
A
S
E
R
\0
7
?
8
?
9
?
10
?
２文字目が一致しない
１文字ずらして
1文字目から照合を開始
0
S
1
X
2
?
3
?
4
?
5
?
6
?
7
?
S
E
A
S
E
R
\0
8
?
9
?
10
?
照合再開位置（３）
(c) ３文字目で不一致
0
S
1
E
2
X
3
?
4
?
5
?
6
?
S
E
A
S
E
R
\0
7
?
8
?
9
?
10
?
３文字目が一致しない
２文字ずらして
1文字目から照合を開始
0
S
1
E
2
X
3
?
4
?
5
?
6
?
7
?
8
?
S
E
A
S
E
R
\0
9
?
10
?
照合再開位置（４）
(d) ４文字目で不一致
0
S
1
E
2
A
3
X
4
?
5
?
6
?
S
E
A
S
E
R
\0
7
?
8
?
9
?
10
?
４文字目が一致しない
３文字ずらして
1文字目から照合を開始
0
S
1
E
2
A
3
X
4
?
5
?
6
?
7
?
8
?
9
?
S
E
A
S
E
R
\0
10
?
照合再開位置（５）
(e) ５文字目で不一致
0
S
1
E
2
A
3
S
4
X
5
?
6
?
S
E
A
S
E
R
\0
7
?
8
?
9
?
10
?
５文字目が一致しない
３文字ずらして
２文字目から照合を開始
0
S
1
E
2
A
3
S
4
X
5
?
6
?
7
?
8
?
9
?
S
E
A
S
E
R
\0
10
?
照合再開位置（６）
(f) ６文字目で不一致
0
S
1
E
2
A
3
S
4
E
5
X
6
?
S
E
A
S
E
R
\0
7
?
8
?
9
?
10
?
６文字目が一致しない
３文字ずらして
３文字目から照合を開始
0
S
1
E
2
A
3
S
4
E
5
X
6
?
7
?
8
?
9
?
S
E
A
S
E
R
\0
10
?
照合再開位置の設定（１）
パターン同士を１文字ずつずらしながら照合する
S
S
S
E
A
S
E
R
S
E
A
S
E
E
A
S
E
R
S
E
A
S
E
A
S
E
R
S
E
A
R
E
S
S
E
A
S
E
R
０
０
S
E
A
S
E
R
０
０
０
S
E
A
S
E
R
０
０
０
１
R
E
R
照合再開位置の設定（２）
パターン同士を１文字ずつずらしながら照合する
S
S
E
E
A
A
S
E
R
S
E
A
S
E
S
E
R
S
E
A
S
E
R
０
０
０
１
２
S
E
R
S
E
A
S
E
R
０
０
０
１
２
０
R
S
E
A
KMP法のプログラム（１）
private int KMP法(string 文字列, string パターン)
{
int P1=1; int P2=0; int[] skip=new int[256];
skip[P1]=0;
while (P1<パターン.Length)
{
if(パターン[P1]==パターン[P2]) skip[++P1]=++P2;
else if(P2==0) skip[++P1]=P2;
else P2=skip[P2];
}
P1=P2=0;
while(P1<文字列.Length && P2<パターン.Length)
{
if(文字列[P1] == パターン[P2]){ P1++; P2++;}
else if(P2 == 0) P1++;
else P2=skip[P2];
}
if(P2==パターン.Length) return(P1 - P2);
return -1;
}
ＫＭＰ法のプログラム（２）
private void button3_Click(object sender, System.EventArgs e)
{
string 文字列
= textBox1.Text;
string パターン = textBox2.Text;
label5.Text=KMP法(文字列, パターン).ToString();
}
（４）ＢＭ法
照合をパターンの末尾から行う方法。
一致しない文字を見つけた場合，
事前に用意した表により移動量を決める。
R. S. BoyerとJ. S. Moore によるアルゴリズム
Boyer-Moore 法，略してＢＭ法と呼ばれる。
BM法の考え方（１）
［例］パターンの後から照合し，ずらしてみよう。
(a)
(b)
(c)
(d)
0
P
1
E
2
T
3
E
4
R
5
P
6
I
P
I
P
R
\0
P
I
P
R
\0
P
I
P
R
\0
P
I
P
R
7
P
8
E
9
R
10
\0
不一致
１文字ずらしても不一致
２文字ずらしても不一致
\0
パターン中にない文字をテキスト中に見つけたら，
そこまでの文字は，すべてスキップできる。
３文字ずらしても不一致
BM法の考え方（２）
［例］一致している場合，１文字前に戻る
0
P
1
E
2
T
3
E
4
R
(a)
P
I
P
E
\0
(b)
P
I
P
E
\0
P
I
P
E
\0
P
I
P
E
(c)
(d)
３文字ずれることになる。
5
P
6
I
7
P
8
E
9
R
10
\0
一致
不一致
１文字ずらしても不一致
\0
２文字ずらしても不一致
BM法の考え方（３）
［例］一致している場合
0
P
5
P
6
I
7
P
8
E
9
R
10
\0
(a)
P
I
P
E
\0
一致
(b)
P
I
P
E
\0
一致
(c)
P
I
P
E
\0
一致
P
I
P
E
\0
一致
(d)
1
E
2
T
3
E
4
R
スキップテーブル
（各文字に出会ったときずらす量）
最初，以下の表を作成しておく。
パターン文字数をN，パターンの最後に出現する位置の添え字をＫとする。
■パターン中にない場合Ｎ
■パターン中にある場合Ｎ－Ｋ－１
K
0
P
1
I
2
P
3
E
2
1
0
（Eのときは，一致の処理）
A
B
C
D
E
F
G
H
I
J
K
L
M
4
4
4
4
0
4
4
4
2
4
4
4
4
N
O
P
Q
R
S
T
U
V
W
X
Y
Z
4
4
1
4
4
4
4
4
4
4
4
4
4
BM法のプログラム（１）
private int BM法(string 文字列, string パターン)
{
int P1=0; int P2=0;
int txtLen =
文字列.Length;
int patLen = パターン.Length;
int[] skip=new int[char.MaxValue+1];
for(P1 =0; P1 <= char.MaxValue; P1++) skip[P1]=patLen;
for(P1 =0; P1 <= patLen - 1;P1++) skip[パターン[P1]]=patLen - P1 -1;
// このとき，P1= patLen-1であることに注意
while(P1<文字列.Length)
{
P2=patLen - 1;
while(文字列[P1] == パターン[P2])
{
if (P2==0) return(P1);
P1--; P2--;
}
P1 += skip[文字列[P1]];
}
return -1;
}
BM法のプログラム（2）
private void button4_Click(object sender, System.EventArgs e)
{
string 文字列
= textBox1.Text;
string パターン = textBox2.Text;
label5.Text=BM法(文字列, パターン).ToString();
}

Download Report