// ■文字列照合の力任せ法, KMP法, BMP法の比較
//    text1に照合対象の文字列
//    text2に照合パターン
//    text3にKMP法、BMP法によるスキップ表
//    text4に下記プログラムのp1の変化
//    を表示します
//   
//    button1, button2, button3を配置し、
//    Clickイベントを指定します。
using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Windows.Forms;

namespace strSearch
{
    public partial class Form1 : Form
    {
        public Form1()
        {
            InitializeComponent();
        }
        private int brute(string str, string pat)
        {
	        int p1,p2,N1,N2; p1=p2=0;N1=str.Length; N2=pat.Length;
            string S = ""; int cnt = 0;
            while(p1<N1 && p2<N2){
                if ((cnt % 8) == 0) S += "\n";
                S += p1.ToString() + " ";
                cnt++;
		        if(str[p1]==pat[p2]){ p1++        ; p2++;}
		        else                { 
                    p1 -= (p2-1); p2=0;
                    if ((cnt % 8) == 0) S += "\n";
                    S += " / ";
                    cnt++;
                }
	        }
            textBox4.Text = S;
	        if(p2==N2) return (p1-p2);
	        return -1;
        }
        private int KMP(string str, string pat){
	        int p1, p2, N1=str.Length, N2=pat.Length;
	        int [] skip=new int[256]; for(p1=0;p1<N2;p1++)skip[p1]=0;
	        p1=1;p2=0;    // スキップテーブル生成
	        while(p1<N2){
		        if(pat[p1]==pat[p2]) skip[++p1] = ++p2;
		        else if(p2==0)       skip[++p1] = p2;
		        else                 p2 = skip[p2];
	        }
            string S = ""; int cnt = 0;
            for (int i = 0; i < N2; i++)
            {
                if ((cnt % 8) == 0) S += "\n"; 
                S += skip[i].ToString() + " ";
            }
            textBox3.Text = S;
	        p1 = p2 =0; S=""; cnt=0;
	        while(p1<N1 && p2<N2){
                if((cnt % 8)==0) S += "\n"; 
                S+= p1.ToString() + " ";
                cnt++;
		        if(str[p1]==pat[p2]){p1++;p2++;}
                else if (p2 == 0)
                {
                    p1++;
                    p2 = skip[p2];
                    if ((cnt % 8) == 0) S += "\n";
                    S += " / ";
                    cnt++;
       
                }
                else
                {
                    p2 = skip[p2];
                    if ((cnt % 8) == 0) S += "\n";
                    S += " / ";
                    cnt++;
                }
	        }
            textBox4.Text=S;
	    if(p2==N2) return p1 - p2; else return -1;
    }
    private int BM(string str, string pat){
	    int p1,p2,N1,N2; p1=p2=0;N1=str.Length; N2=pat.Length;
	    int [] skip=new int[256];
	    for(p1=0;p1<256;p1++) skip[p1]=N2;//スキップテーブル生成
	    for(p1=0;p1<=N2-1;p1++)skip[pat[p1]] = N2 - p1 - 1;
        string S = ""; int cnt = 0;
	    for(int i=0; i<256; i++) {//スキップテーブル表示
		    if(i %8==0) S+="\n";
            S+= skip[i].ToString() +" ";
	        }
            textBox3.Text = S;
	        p1 = N2-1; //BM法におけるp1の値
            S=""; cnt=0;
	        while(p1<N1){
		        if((cnt % 8)==0) S += "\n";
                S+= p1.ToString() + " ";
                cnt++;
			    for(p2=N2-1;str[p1]==pat[p2];p1--, p2--){
                    if (p2 != (N2 - 1))
                    {
                        if ((cnt % 8) == 0) S += "\n";
                        S += p1.ToString() + " ";
                        cnt++;
                    }
			        if(p2==0) return p1;
		        }
                textBox4.Text=S;
		        p1+=skip[str[p1]];
                if ((cnt % 8) == 0) S += "\n";
                S += " / ";
                cnt++; ;
	        }
            textBox4.Text = S;
	        return -1;
        }
        private void button1_Click(object sender, EventArgs e)
        {
            	string str=textBox1.Text, pat=textBox2.Text;
            	label5.Text="照合結果 " +brute(str,pat).ToString();
	    }

        private void button2_Click(object sender, EventArgs e)
        {
            string str = textBox1.Text, pat = textBox2.Text;
            label5.Text = "照合結果 " + KMP(str, pat).ToString();
	    }

        private void button3_Click(object sender, EventArgs e)
        {
            string str = textBox1.Text, pat = textBox2.Text;
            label5.Text = "照合結果 " + BM(str, pat).ToString();
        }
    }
}