首页 > 其他 > 详细

数据结构实验4——字符串匹配

时间:2019-10-18 13:41:03      阅读:56      评论:0      收藏:0      [点我收藏+]

挺好写的

贴代码:

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <windows.h>
  4 #include <cwchar>
  5 
  6 using namespace std;
  7 
  8 const int max_str_len = 255;//用户在255(1字节)以内定义最大串长
  9 typedef char SString[max_str_len];//0号单元存放串的长度
 10 
 11 //生成一个值等于chars的串T
 12 void StrAssign(SString T, char * chars){
 13     for(int i = 0; chars[i] != \0; i ++ ){
 14         T[i + 1] = chars[i];
 15         T[0] = char(i + 1);
 16     }
 17 }
 18 
 19 void StrPrint(SString T){
 20     int len = (int)T[0];
 21     for(int i = 1; i <= len; i ++ ){
 22         printf("%c", T[i]);
 23     }
 24     cout<<endl;
 25 }
 26 
 27 int StrLength(SString S){
 28     int len = (int)S[0];
 29     return len;
 30 }
 31 
 32 bool Concat(SString T, SString S1, SString S2){
 33     int len1 = (int)S1[0];
 34     int len2 = (int)S2[0];
 35     if(len1 + len2 > max_str_len) return false;
 36     T[0] = char(len1 + len2);
 37     for(int i = 1; i <= len1; i ++ ){
 38         T[i] = S1[i];
 39     }
 40     for(int i = len1 + 1; i <= len1 + len2; i ++ ){
 41         T[i] = S2[i - len1];
 42     }
 43     return true;
 44 }
 45 
 46 //BF算法(暴力
 47 //返回子串t在主串中第pos个字符开始第一次出现的位置。若不存在,则返回值为0
 48 //t非空, 1 <= pos <= s.length
 49 int index(SString s, SString t, int pos){
 50     int i = pos, j = 1;
 51     while(i <= StrLength(s) && j <= StrLength(t)){
 52         if(s[i] == t[j]){
 53             i ++ ;
 54             j ++ ;
 55         }
 56         else{
 57             i = i - j + 2;
 58             j = 1;
 59         }
 60     }
 61     if(j > StrLength(t))
 62         return i - StrLength(t);
 63     else return 0;
 64 }
 65 
 66 //求next数组
 67 void get_next(SString t, int next[]){
 68     int i = 1;
 69     next[1] = 0;
 70     int j = 0;
 71     while(i < StrLength(t)){
 72         if(j == 0 || t[i] == t[j]){
 73             i ++ ;
 74             j ++ ;
 75             next[i] = j;
 76         }
 77         else j = next[j];
 78     }
 79 }
 80 
 81 //kmp算法
 82 int kmp(SString s, SString t, int pos, int next[]){
 83     int i = pos;
 84     int j = 1;
 85     while(i <= StrLength(s) && j <= StrLength(t)){
 86         if(j == 0 || s[i] == t[j]){
 87             i ++ ;
 88             j ++ ;
 89         }
 90         else
 91             j = next[j];
 92     }
 93     if(j > StrLength(t))
 94         return i - StrLength(t);
 95     else
 96         return 0;
 97 }
 98 
 99 int main()
100 {
101     SetConsoleOutputCP(65001);
102     int i, *next;
103     char ch1[80], ch2[80];
104     SString s1, s2, s, sub;//定义串,第一个单元储存串的长度
105     cout<<"请输入第一个字符串:";
106     cin>>ch1;
107     StrAssign(s1, ch1);
108     StrPrint(s1);
109     cout<<"请输入第二个字符串:";
110     cin>>ch2;
111     StrAssign(s2, ch2);
112     StrPrint(s2);
113     cout<<"-------------------------\n";
114     cout<<"第一个字符串长度为:"<<StrLength(s1)<<endl;
115     cout<<"第二个字符串长度为:"<<StrLength(s2)<<endl;
116     if(!Concat(s, s1, s2)){
117         cout<<"字符串过长"<<endl;
118         return 0;
119     }
120     else{
121         cout<<"主串长度为:"<<StrLength(s)<<endl;
122         cout<<"主串为:";
123         StrPrint(s);
124     }
125     cout<<"请输入子串:";
126     cin>>ch2;
127     StrAssign(sub, ch2);
128     cout<<"子串长度为:"<<StrLength(sub)<<endl;
129     cout<<"----BE匹配算法及实现------\n";
130     i = index(s, sub, 1);
131     if(i)
132         printf("主串和子串在第%d个字符处首次匹配\n", i);
133     else
134         printf("主串和子串匹配不成功\n");
135     cout<<"----KMP匹配算法及实现----\n";
136     next = new int[StrLength(sub) + 1];
137     get_next(sub, next);
138     printf("子串的next数组为:");
139     for(int i = 1; i <= StrLength(sub); i ++ ){
140         cout<<*(next + i);
141     }
142     cout<<endl;
143     i = kmp(s, sub, 1, next);
144     if(i)
145         printf("主串和子串在第%d个字符处首次匹配\n", i);
146     else
147         printf("主串和子串匹配不成功\n");
148     return 0;
149 }

 

数据结构实验4——字符串匹配

原文:https://www.cnblogs.com/moomight/p/11697708.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!