様式９ +-------------------------------------+----------------+----------------------+ | ｼｽﾃﾑ名(ｺｰﾄﾞ): ＡＬＧＯＰＡＫ | | システム報告書概要 | +-------------------------------------+ +----------------------+ | ﾓｼﾞｭｰﾙ名(ｺｰﾄﾞ): KMPSCAN (A403) | ﾗｲﾌﾞﾗﾘ-登録番号: | +-------------------------------------+---------------------------------------+ | 作成者･学生番号: 増沢善子　21SS1159 | 文書作成者･学生番号: 増沢善子21SS1159 | +-------------------------------------+---------------------------------------+ | 作成期間: 62/ 1/ ー / / | 文書作成期間: 62/ 2/ ー / / | +-------------------------------------+---------------------------------------+ | 親モジュール: ＡＬＧＯＳ | 子モジュール: | +-------------------------------------+---------------------------------------+ | 講義名・課題名: 卒業研究 | 参考文献(著者名、書名、出版社、発行年)| +-------------------------------------+ | | 開発形態: 移植 | SARA BAASE,COMPUTER ALGORITHM, | +-------------------------------------+ | | 形式: サブルーチン | ADDISON WESLEY,1978 | +-------------------------------------+---------------------------------------+ | 利用対象者: 一般 | 格納ﾒﾃﾞｨｱ形式: フロッピーディスク | +-------------------------------------+---------------------------------------+ | 目的（問題解説、機能解説−制限事項）| 格納ﾒﾃﾞｨｱ番号、ﾌｧｲﾙ名: | | +---------------------------------------+ | | 記述言語・走行ＯＳ: TURBO PASCAL | | ＳＯＲＴＩＮＧ の +---------------------------------------+ | | 走行条件（ハードウェア、ソフトウェア）| | サブルーチン プログラム | ＰＣ−９８０１，ＭＳ−ＤＯＳ | | | | | | | +-------------------------------------+---------------------------------------+ | キーワード（適用分野、手法など） ： | 分類コード（ＣＲコードを使用） ： | | KMP SCAN | | +-------------------------------------+---------------------------------------+ | 呼び出し法: | | KMPSCAN (N,M,S,P) | +-----------------------------------------------------------------------------+ | 操作手順(ｺﾝﾌﾟﾘｰﾄﾌﾟﾛｸﾞﾗﾑ(ﾒｲﾝﾌﾟﾛｸﾞﾗﾑ)の場合:1.システム起動手順､2.データ入出力 | | 手順と形式､3.終了手順) | | (ｻﾌﾞﾙｰﾁﾝの場合:1.呼び出し形式-引き数の並べ方-､2.親ルーチン､3.子ルー | | チン､4.その他) | | | | | | １， 入力 （Ｎ）： 文字列 の 長さ | | | | （Ｍ）： 探索文字列 の 長さ | | | | 入出力 （Ｓ）： 文字列 | | | | （Ｐ）： 探索文字列 （パターン） | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | +-----------------------------------------------------------------------------+ 注. システム１つにつき１枚作成 必要な場合モジュール１つにつき１枚作成(ｲﾝﾀｰﾌｪｰｽ仕様書-様式１-に追加) 様式７ +-------------------------------------+----------------+----------------------+ | システム名: ＡＬＧＯＰＡＫ | | 問題解説 | +-------------------------------------+ +----------------------+ | モジュール名: KMPSCAN (A403) | ﾗｲﾌﾞﾗﾘ-登録番号: | +-------------------------------------+---------------------------------------+ | 作成者: 小平初美 10SS1121 | 文書作成者: 小平初美 10SS1121 | +-------------------------------------+---------------------------------------+ | 作成期間: 58/07/ ー 54/09/ | 文書作成期間: 59/11/ ー 59/12/ | +-------------------------------------+---------------------------------------+ | | | ＫＭＰ ＳＣＡＮ ＡＬＧＯＲＩＴＨＭ は，（Ａ４０２） で組み立てた | | | | フローチャートを使って subject を パターンmatching するものである。 | | | | 与えられたパターンの文字列をsubjectの長さの和に比例する範囲中で，すべ | | | | て見付け出す。 プログラムは，例えば与えられた "パターン" という文字列を | | | | 見付けるために，時々文字列の最後まで探索する必要がある。つまり，subject | | | | の相接する部分文字列に発生するパターンのすべての位置か，最も左の位置を | | | | みつければよい。 | | | | 例： Ｐ＝ ａｂｃａｂｃａｃａｂ | | | | Ｓ＝ ａａｃａａｂｃａｂｃａｂｃａｃａｂｃ | | | | パターンに一致するものを捜すための明らかな方法は，subgectの | | | | 最初の位置から１つずつ捜して試し，妥当でない文字をみつけるとす | | | | ぐにそれを捨てる。 頭の文字が一致した場合，次のいくつかの文字 | | | | を調べている間にパターンは固定しておく。 | | | | | | ａｂｃａｂｃａｃａｂ | | | | ａａｃａａｂｃａｂｃａｂｃａｃａｂｃ | | ↑ | | | | | | ａｂｃａｂｃａｃａｂ | | | | ａａｃａａｂｃａｂｃａｂｃａｃａｂｃ | | ↑ | | | | ａｂｃａｂｃａｃａｂ | | | | ａａｃａａｂｃａｂｃａｂｃａｃａｂｃ | | ↑ | | ．．．．．．．．．．．． | | ．．．．．．．．．．．． | | | | ａｂｃａｂｃａｂａｂ | | | | ａａｃａａｂｃａｂｃａｂｃａｃａｂｃ | | ↑ | | | | | | | | | +-----------------------------------------------------------------------------+ 様式６ +-------------------------------------+----------------+----------------------+ | システム名: ＡＬＧＯＰＡＫ | | アルゴリズム流れ図 | +-------------------------------------+ +----------------------+ | モジュール名: KMPSCAN (A403) | ﾗｲﾌﾞﾗﾘ-登録番号: | +-------------------------------------+---------------------------------------+ | 作成者: 小平初美 10SS1121 | 文書作成者: 小平初美 10SS1121 | +-------------------------------------+---------------------------------------+ | 作成期間: 58/07/ ー 58/09/ | 文書作成期間: 59/11/ ー 59/12/ | +-------------------------------------+---------------------------------------+ | | | ++-------++ +---------+ | | !!KMPTEST!! !I:=1; ! | | !!2 !!---->! J:=1; ! | | !!(A403) !! ^ ! ! | | ++-------++ ! +---------+ | | ! ! | | ! +--------++ +--------++ +---------+ | | ! !WHILE !! !WHILE J!>0 ﾄ P[!!---->! FLINK(J)! | | ! ! !! ^ !J]<>S[I]!! ! ! | | ! +--------++ ! +--------++ +---------+ | | ! ! ! ! | | ! ! ! +-------+ +-----+ | | ! ! ! !IF + /WRITE/ | | ! ! !-! J=M +----> /'SUCC/ | | ! ! ! + ^ /ESS' / | | ! ! +-------+ ! +-----+ | | ! ! ! ! | | ! ! ! +---------+ | | ! ! ! !I:=I+1; ! | | ! ! !-! J:=J+1 ! | | ! ! ! ! | | ! ! +---------+ | | ! ! | | ! +-----+ | | ! /WRITE/ | | !- / 'FAI/ | | /LURE'/ | | +-----+ | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | +-----------------------------------------------------------------------------+ 様式９ +-------------------------------------+----------------+----------------------+ | ｼｽﾃﾑ名(ｺｰﾄﾞ): ＡＬＧＯＰＡＫ | | システム報告書概要 | +-------------------------------------+ +----------------------+ | ﾓｼﾞｭｰﾙ名(ｺｰﾄﾞ): CKMPSCAN (P403) | ﾗｲﾌﾞﾗﾘ-登録番号: | +-------------------------------------+---------------------------------------+ | 作成者･学生番号: 増沢善子 21SS1159 | 文書作成者･学生番号: 増沢善子21SS1159 | +-------------------------------------+---------------------------------------+ | 作成期間: 62/01/ ー / / | 文書作成期間: 62/ 2/ ー / / | +-------------------------------------+---------------------------------------+ | 親モジュール: ＡＬＧＯＰＡＫ | 子モジュール: KMPTEST (A402) | +-------------------------------------+---------------------------------------+ | 講義名・課題名: 卒業研究 | 参考文献(著者名、書名、出版社、発行年)| +-------------------------------------+ | | 開発形態: 移植 | SARA BAASE,COMPUTER ALGORITHM, | +-------------------------------------+ | | 形式: コンプリート | ADDISON WESLEY,1978 | +-------------------------------------+---------------------------------------+ | 利用対象者: 一般 | 格納ﾒﾃﾞｨｱ形式: フロッピーディスク | +-------------------------------------+---------------------------------------+ | 目的（問題解説、機能解説−制限事項）| 格納ﾒﾃﾞｨｱ番号、ﾌｧｲﾙ名: | | +---------------------------------------+ | | 記述言語・走行ＯＳ: TURBO PASCAL | | ＳＯＲＴＩＮＧ の +---------------------------------------+ | | 走行条件（ハードウェア、ソフトウェア）| | コンプリート プログラム | ＰＣ−９８０１，ＭＳ−ＤＯＳ | | | | | | | +-------------------------------------+---------------------------------------+ | キーワード（適用分野、手法など） ： | 分類コード（ＣＲコードを使用） ： | | KMP SCAN | | +-------------------------------------+---------------------------------------+ | 呼び出し法: CKMPSCAN | | データ | +-----------------------------------------------------------------------------+ | 操作手順(ｺﾝﾌﾟﾘｰﾄﾌﾟﾛｸﾞﾗﾑ(ﾒｲﾝﾌﾟﾛｸﾞﾗﾑ)の場合:1.システム起動手順､2.データ入出力 | | 手順と形式､3.終了手順) | | (ｻﾌﾞﾙｰﾁﾝの場合:1.呼び出し形式-引き数の並べ方-､2.親ルーチン､3.子ルー | | チン､4.その他) | | 1. ＞ ＣＫＭＰＳＣＡＮ． ＳＲＣ　　　　　 | | | | 　　　　　　　　　　　　　　　　　　　　　　　　　 | | | | 　　　　　　　　　　 | | | | データ | | | | ２， 1)入力データ | | | | Ｐ：パターン Ｓ：subject列 （Ｐの長さ; m≧1） | | | | （Ｓの長さ; n≧0） | | | | ＦＬＩＮＫ（失敗Ｌｉｎｋｓの配列） | | | | 2)出力データ | | | | ＳＵＣＣＥＲＳＳ，ＦＡＩＬＵＲＥ の表示 | | | | | | | | | | | | | | | +-----------------------------------------------------------------------------+ 注. システム１つにつき１枚作成 必要な場合モジュール１つにつき１枚作成(ｲﾝﾀｰﾌｪｰｽ仕様書-様式１-に追加)