８．文字列処理 ８．１　Ｃ＃の文字列 Ｃ＃では， “ABCD”のように文字列を２重引用符で挟んで指定します。ASCIIコード体系のとき，以下のような内部形式となります。 1 1 文字 ‘A’ ナル文字 1 1 文字 ‘B’ A B C D \0 1 1 1 文字 ‘C’ 1 1 文字 ‘D’ ナル文字‘\0’

文字列の内部表現 文字列の内部形式を 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を返す。大文字と小文字は区別される。 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）とは， ８．３　文字列探索 （１）文字列探索とは 文字列探索（string searching）とは， ある文字列の中に，別の文字列が含まれているかどうか， 含まれている場合は，その位置を示すこと。 探索される側の文字列：テキスト（text） 探し出すための文字列：パターン（pattern）

（２）力まかせ法（単純法，素朴法） 力まかせ法（brute forth method）の手順 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 (a) P E T E R P I P E R \0 P I P \0 ３文字目が一致しない 1 2 3 4 5 6 7 8 9 10 (b) P E T E R P I P E R \0 P I P \0 １文字目が一致しない 1 2 3 4 5 6 7 8 9 10 (c) P E T E R P I P E R \0 P I P \0 １文字目が一致しない

力まかせ法の手順２ 力まかせ法（brute forth method）の手順 1 2 3 4 5 6 7 8 9 10 P E T E R 1 2 3 4 5 6 7 8 9 10 P E T E R P I P E R \0 (d) P I P \0 １文字目が一致しない 1 2 3 4 5 6 7 8 9 10 (e) P E T E R P I P E R \0 P I P \0 １文字目が一致しない 1 2 3 4 5 6 7 8 9 10 (f) P E T E R P I P E R \0 P I P \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法の考え方 ［例］パターン移動の際，何文字目から照合を再開するかを事前に決めておく。 1 2 3 4 5 6 7 8 9 10 (a) 1 2 3 4 5 6 7 8 9 10 (a) P S E A S E R P E R \0 S E A S E R \0 1文字目が一致しない 1 2 3 4 5 6 7 8 9 10 (b) P S E A S E D P E R \0 S E A S E R \0 6文字目が一致しない 1 2 3 4 5 6 7 8 9 10 (c) P S E A S E R P E R \0 （３文字目から照合） S E A S E R \0

照合再開位置（１） (a) １文字目で不一致 1 2 3 4 5 6 7 8 9 10 P ? ? ? ? ? ? ? ? ? ? S E 1 2 3 4 5 6 7 8 9 10 P ? ? ? ? ? ? ? ? ? ? S E A S E R \0 1文字目が一致しない 1文字目から照合を開始 1 2 3 4 5 6 7 8 9 10 P ? ? ? ? ? ? ? ? ? ? S E A S E R \0

照合再開位置（２） (b) ２文字目で不一致 1 2 3 4 5 6 7 8 9 10 S X ? ? ? ? ? ? ? ? ? S E 1 2 3 4 5 6 7 8 9 10 S X ? ? ? ? ? ? ? ? ? S E A S E R \0 ２文字目が一致しない １文字ずらして 1文字目から照合を開始 1 2 3 4 5 6 7 8 9 10 S X ? ? ? ? ? ? ? ? ? S E A S E R \0

照合再開位置（３） (c) ３文字目で不一致 1 2 3 4 5 6 7 8 9 10 S E X ? ? ? ? ? ? ? ? S E 1 2 3 4 5 6 7 8 9 10 S E X ? ? ? ? ? ? ? ? S E A S E R \0 ３文字目が一致しない ２文字ずらして 1文字目から照合を開始 1 2 3 4 5 6 7 8 9 10 S E X ? ? ? ? ? ? ? ? S E A S E R \0

照合再開位置（４） (d) ４文字目で不一致 1 2 3 4 5 6 7 8 9 10 S E A X ? ? ? ? ? ? ? S E 1 2 3 4 5 6 7 8 9 10 S E A X ? ? ? ? ? ? ? S E A S E R \0 ４文字目が一致しない ３文字ずらして 1文字目から照合を開始 1 2 3 4 5 6 7 8 9 10 S E A X ? ? ? ? ? ? ? S E A S E R \0

照合再開位置（５） (e) ５文字目で不一致 1 2 3 4 5 6 7 8 9 10 S E A S X ? ? ? ? ? ? S E 1 2 3 4 5 6 7 8 9 10 S E A S X ? ? ? ? ? ? S E A S E R \0 ５文字目が一致しない ３文字ずらして ２文字目から照合を開始 1 2 3 4 5 6 7 8 9 10 S E A S X ? ? ? ? ? ? S E A S E R \0

照合再開位置（６） (f) ６文字目で不一致 1 2 3 4 5 6 7 8 9 10 S E A S E X ? ? ? ? ? S E 1 2 3 4 5 6 7 8 9 10 S E A S E X ? ? ? ? ? S E A S E R \0 ６文字目が一致しない ３文字ずらして ３文字目から照合を開始 1 2 3 4 5 6 7 8 9 10 S E A S E X ? ? ? ? ? S E A S E R \0

照合再開位置の設定（１） パターン同士を１文字ずつずらしながら照合する S E A S E R S E A S E R S E A S E ０ ０ S E A S E R S E A S E R S E A S E R ０ ０ ０ S E A S E R S E A S E R S E A S E R ０ ０ ０ １

照合再開位置の設定（２） パターン同士を１文字ずつずらしながら照合する S E A S E R S E A S E R S E A S E ０ ０ ０ １ ２ S E A S E R S E A S E R S E A S E R ０ ０ ０ １ ２ ０

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法の考え方（１） ［例］パターンの後から照合し，ずらしてみよう。 1 2 3 4 5 6 7 8 9 10 P E T E R P I 1 2 3 4 5 6 7 8 9 10 P E T E R P I P E R \0 (a) P I P R \0 不一致 (b) P I P R \0 １文字ずらしても不一致 (c) P I P R \0 ２文字ずらしても不一致 (d) P I P R \0 ３文字ずらしても不一致 パターン中にない文字をテキスト中に見つけたら， そこまでの文字は，すべてスキップできる。

BM法の考え方（２） ［例］一致している場合，１文字前に戻る 1 2 3 4 5 6 7 8 9 10 P E T E R P I P E 1 2 3 4 5 6 7 8 9 10 P E T E R P I P E R \0 (a) P I P E \0 一致 (b) P I P E \0 不一致 (c) P I P E \0 １文字ずらしても不一致 (d) P I P E \0 ２文字ずらしても不一致 ３文字ずれることになる。

BM法の考え方（３） ［例］一致している場合 1 2 3 4 5 6 7 8 9 10 P E T E R P I P E R \0 (a) 1 2 3 4 5 6 7 8 9 10 P E T E R P I P E R \0 (a) P I P E \0 一致 P I P E \0 (b) 一致 P I P E \0 (c) 一致 P I P E \0 一致 (d)

スキップテーブル （各文字に出会ったときずらす量） 最初，以下の表を作成しておく。 　　　パターン文字数をN，パターンの最後に出現する位置の添え字をＫとする。 　　　■パターン中にない場合　Ｎ 　　　■パターン中にある場合　Ｎ－Ｋ－１ K 1 2 3 P I P E 2 1 （Eのときは，一致の処理） A B C D E F G H I J K L M 4 4 4 4 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(); }