[資料結構] 資料搜尋

字串搜尋

本程式只是一篇範例，用於搜尋文章中的關鍵字

並沒有使用到課本的失敗函數，如果想要加速搜尋請自行修改pmatch函數!

本程式是我教導別人一步一步慢慢寫出來的，可能會有許多問題(參數命名、...等)

但如果想學字串搜尋的人是個可以參考的程式!

當如果會這個程式之後，那麼我們就可以直接使用 strstr 來做字串搜尋!這樣會比較方便一點~ 不過一開始對於寫程式不熟的人來說，最好可以練習一下怎麼重頭自己寫!

使用版本:VS2010
載點:
字串搜尋.rar (13.6 MB)
載點1  載點2
挑一個下載即可~

程式碼預覽(因為這邊打註解會怪怪的，所以要看註解請下載檔案)
以下程式碼寫得很不好，有空我在修飾，而且沒有呼叫到fail!

/* @作者 atien 阿添
使用請注意
本程式只是一篇範例，用於搜尋文章中的關鍵字
並沒有使用到課本的失敗函數，如果想要加速搜尋請自行修改pmatch函數!
本程式是我教導別人一步一步慢慢寫出來的，可能會有許多問題(參數命名、...等)
但如果想學字串搜尋的人是個可以參考的程式!

s為要找的字 pat 為文章
     i=0
  ↓
s  = a b c d 
pat= a b c d a b a b c d
     ↑
  j=1

*/

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <iostream>
#include <windows.h> 

using namespace std;
#define max_string_size 100 
#define max_pattern_size 10000 
/*顏色定義*/
#define RED FOREGROUND_RED
#define GREEN FOREGROUND_GREEN
#define BLUE FOREGROUND_BLUE 
#define setcolor(c) SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),c)

int failure[max_pattern_size]; 
char str[max_string_size];
char pat[max_pattern_size]; 
int sav[max_string_size];//存儲找到的位置
int num=0;//數找到幾個


/*失敗函數*/
void fail(char *pat)
{ 
 int n = strlen(pat); 
 int i=0,j=0;   
 failure[0] = -1; 
 for(j=1; j<n; j++) 
 {
  i=failure[j-1];  
  while((pat[j] != pat[i+1]) && (i >= 0))
   i=failure[i];
  if(pat[j] == pat[i+1])
   failure[j] = i+1;
  else failure[j] = -1;
 }
}
/*字串比對*/
void pmatch(char *string,char *pat) 
{
     
 int i,j;
 char *k;
 int lens = strlen(string);
 int lenp = strlen(pat);   
 
 for(j=0,i=0;j<lenp;j++)  
 {
  if(string[i] == pat[j])  
  {//找到相同的字，還沒找完
       i++;
      }
  else
   i=0;//找錯字

  if(i==strlen(string))
  {//找到了!!
  sav[num]=j;
  num++;
  }
 }
}

int main()
{
 
 FILE *fp = fopen("abc.txt","r");
 char c;
 int i=0;
 while((c=getc(fp))!=EOF)
 {
 pat[i]=c;
 i++;
 }

 printf("請輸入要找的字"); 
 cin >> str;
 printf("\n");
 //fail(pat);// 本程式並沒有使用到此副程式，請自行修正!

 /*字串比對*/
 pmatch(str,pat);
 /*印出標記色*/
 int count=strlen(str);
 for(int y=0,j=0;y<strlen(pat);y++)
 {
  if(y<=sav[j] && (y>=sav[j]-strlen(str)+1)){
  setcolor(12);//找到關鍵字印的顏色
  count--;//要印出整個長度的顏色
   if(count==0)
   {/*換找下一個*/
    count=strlen(str);
    j++;
   }
  }
  else
   setcolor(RED+GREEN+BLUE);//非關鍵字的顏色
  cout << pat[y];
 }
 fclose (fp);
    system("pause");
 return 0;
}