仅供课外学习使用，任何个人与机构不得利用此文章进行任何形式的作弊。
01基于BF算法的病毒感染检测
#include
#include
#include
using namespace std;
#define MAXSIZE 2000
//- - - - - 串的堆式顺序存储结构- - - - -
typedef struct
{
char *ch; //若是非空串，则按串长分配存储区，否则ch为NULL
int length; //串的当前长度
}HString;
int Index_BF(HString S,HString T,int pos)
{//返回模式T在主串S中第pos个字符开始第一次出现的位置。若不存在，则返回值为0
//其中，T非空，1≤pos≤StrLength(S)
int i = pos - 1, j = 0;
while(i < S.length && j < T.length)
{
if(S.ch[i] == T.ch[j])
{
i++;
j++;
}
else
{
i = i - j + 1;
j = 0;
}
}
if(j >= T.length)
return i - T.length + 1;
else return 0;
}
bool Virus_detection(HString Virus,HString Person)
{//判断是否匹配，如果可以，返回true，否则返回false
//模式匹配算法调用Index_BF函数
bool flag = false;
if(Index_BF(Person, Virus, 1))
return true;
for(int i = 0; i <= Virus.length; i++)
{
char c = Virus.ch[0];
for(int j = 1; j < Virus.length; j++)
Virus.ch[j - 1] = Virus.ch[j];
Virus.ch[Virus.length - 1] = c;
if(Index_BF(Person, Virus, 1))
{
flag = true;
break;
}
}
return flag;
}
int main()
{
int num,m,flag,i,j; char Vir[1000];
HString Virus,Person;
char a[MAXSIZE],b[MAXSIZE];//a存入病毒的DNA序列，b存入人的DNA序列
while(cin>>a>>b)
{
Virus.ch=new char[1000];
Person.ch=new char[1000];
if(strcmp(a,"0")==0&&strcmp(b,"0")==0)
break;
strcpy(Virus.ch,a);
strcpy(Person.ch,b);
Virus.length=strlen(Virus.ch);
Person.length=strlen(Person.ch);
if(Virus_detection(Virus,Person))
cout<<"YES"< else cout<<"NO"< }//while return 0; } 02基于BF算法的网络入侵检测 #include "iostream" #include "cstring" #include using namespace std; #define MAXLEN 5000 //串的最大长度 typedef struct{ char *ch; //存储串的一维数组 int length; //串的当前长度 }HString; void InputRule(HString ip[],int n) {//输入n条规则，并将其中的n个ip地址存放到ip数组 for(int i = 0; i < n; i++) ip[i].ch = new char[100]; for(int i = 0; i < n; i++) { string ss; int a, b; getline(cin, ss); for(int j = 0; j < (int)ss.length(); j++) { if(ss[j] == ':' && ss[j - 1] == 'p') a = j + 1; if(ss[j] == ' ' && ss[j + 1] == 'm') b = j - 1; } for(int j = a, k = 0; j <= b; j++, k++) { ip[i].ch[k] = ss[j]; ip[i].length = b - a + 1; } } } void InputLog(HString &log,int m) {//输入m条日志，并合并存放到log delete log.ch; log.ch=(char *)malloc(sizeof(char)*10000); string s; for(int i = 0; i < m; i++) { string ss; getline(cin, ss); s += ss; } for(int i = 0; i < (int)s.length(); i++) log.ch[i] = s[i]; log.length = (int)s.length(); } int Index_BF(HString S, HString T) {//简单模式匹配算法,S为主串(目标串)，T为子串(模式串)。 //匹配成功返回主串中所含子串第一次出现的位置，否则返回-1。 int i = 0, j = 0; while(i < S.length && j < T.length) { if(S.ch[i] == T.ch[j]) { i++; j++; } else { i = i - j + 1; j = 0; } } if(j >= T.length) return i - T.length; else return -1; } int main() { int n,m; cin>>n>>m; getchar(); HString ip[5000];//ip数组存放n个ip地址 InputRule(ip,n); HString log; log.ch=(char *)malloc(sizeof(char)*5000); //这里开小了 strcpy(log.ch,""); log.length=0; InputLog(log,m); for(int i=0;i { if(Index_BF(log,ip[i])!= -1) { cout<<"Intrusion."< return 0; } } cout<<"No Intrusion."< return 0; } 03基于KMP算法的网络入侵检测 #include "iostream" #include "cstring" #include using namespace std; #define MAXLEN 5000 //串的最大长度 typedef struct{ char *ch; //存储串的一维数组 int length; //串的当前长度 }HString; void InputRule(HString ip[],int n) {//输入n条规则，并将其中的n个ip地址存放到ip数组 for(int i = 0; i < n; i++) ip[i].ch = new char[100]; for(int i = 0; i < n; i++) { string ss; int a, b; getline(cin, ss); for(int j = 0; j < (int)ss.length(); j++) { if(ss[j] == ':' && ss[j - 1] == 'p') a = j + 1; if(ss[j] == ' ' && ss[j + 1] == 'm') b = j - 1; } for(int j = a, k = 0; j <= b; j++, k++) { ip[i].ch[k] = ss[j]; ip[i].length = b - a + 1; } } } void InputLog(HString &log,int m) {//输入m条日志，并合并存放到log，返回log的length delete log.ch; log.ch=(char *)malloc(sizeof(char)*10000); string s; for(int i = 0; i < m; i++) { string ss; getline(cin, ss); s += ss; } for(int i = 0; i < (int)s.length(); i++) log.ch[i] = s[i]; log.length = (int)s.length(); } void GetNext(HString pattern,int* next) {//求模式串pattern的next函数值并存入数组next next[0] = -1; int k = -1; for(int q = 1; q <= pattern.length; q++) { while(k > -1 && pattern.ch[k + 1] != pattern.ch[q]) k = next[k]; if(pattern.ch[k + 1] == pattern.ch[q]) k++; next[q] = k; } } int Index_KMP(HString target,HString pattern,int* next) {//KMP匹配算法,target为主串，pattern为子串。 //匹配成功返回主串中所含子串第一次出现的位置，否则返回-1。 //调用GetNext函数获取模式串的next数组 GetNext(pattern, next); int k = -1, i = 0; for(i = 0; i < target.length; i++) { while(k > -1 && pattern.ch[k + 1] != target.ch[i]) k = next[k]; if(pattern.ch[k + 1] == target.ch[i]) k++; if(k == pattern.length - 1) return i - pattern.length + 1; } return -1; } int main() { int n,m; cin>>n>>m; getchar(); HString ip[5000];//ip数组存放n个ip地址 InputRule(ip,n); HString log; log.ch=(char *)malloc(sizeof(char)*5000); strcpy(log.ch,""); log.length=0; InputLog(log,m); for(int i=0;i { int *next=new int[ip[i].length]; if(Index_KMP(log,ip[i],next)!= -1) { cout<<"Intrusion."< return 0; } } cout<<"No Intrusion."< return 0; } 04基于BM算法的网络入侵检测 #include #include #include "cstring" using namespace std; #define ASCII_SIZE 256 //ASCII码共256位，可表示所有字符，作为坏字符数组的大小 #define MAXLEN 5000 //串的最大长度 typedef struct{ char *ch; //存储串的一维数组 int length; //串的当前长度 }HString; void InputRule(HString ip[],int n) {//将输入的n个ip地址存放到ip数组 for(int i = 0; i < n; i++) ip[i].ch = new char[100]; for(int i = 0; i < n; i++) { string ss; int a, b; getline(cin, ss); for(int j = 0; j < (int)ss.length(); j++) { if(ss[j] == ':' && ss[j - 1] == 'p') a = j + 1; if(ss[j] == ' ' && ss[j + 1] == 'm') b = j - 1; } for(int j = a, k = 0; j <= b; j++, k++) { ip[i].ch[k] = ss[j]; ip[i].length = b - a + 1; } } } void InputLog(HString &log,int m) {//将输入的m条日志合并存放到log，返回log的总长度 delete log.ch; log.ch=(char *)malloc(sizeof(char)*10000); string s; for(int i = 0; i < m; i++) { string ss; getline(cin, ss); s += ss; } for(int i = 0; i < (int)s.length(); i++) log.ch[i] = s[i]; log.length = (int)s.length(); } void getBC(HString pattern,int *bc) {//得到坏字符bc数组 for (int i = 0; i < ASCII_SIZE; i++) { bc[i] = -1; } for (int i = 0; i < pattern.length; i++) { bc[(int)pattern.ch[i]] = i; } } void getGS(HString pattern,int *suffix,bool *prefix) {//得到好后缀gs，其中suffix为int类型数组存储后缀字符对应前面的位置，prefix为bool类型数组存储是否存在匹配的前缀字符串 //suffix和prefix共同构成好后缀数组 // suffix = new int[MAXLEN]; // prefix = new bool[MAXLEN]; int n = pattern.length; for (int i = 0; i < n - 1; i++) { suffix[i] = -1; prefix[i] = false; } for (int i = 0; i < n - 1; i++) { int j = i; int k = 0; while (j >= 0 && pattern.ch[j] == pattern.ch[n - 1 - k]) { j--; k++; suffix[k] = j + 1; } if (j == -1) prefix[k] = true; } } int getGSMove(int *suffix,bool *prefix,int bc_pos,int pattern_length) {//利用suffix和prefix数组，返回好后缀移动的次数 //bc_pos表示坏字符BC的位置（后一位为好后缀起点位置） int len = pattern_length - bc_pos - 1; if (suffix[len] != -1) { return bc_pos + 1 - suffix[len]; } for (int i = bc_pos + 2; i < pattern_length; i++) { if (prefix[pattern_length - i]) return i; } return 0; } int Index_BM(HString str,HString pattern) {//在str.ch中匹配pattern.ch，匹配成功返回主串中所含子串第一次出现的位置，否则返回-1。 //分别求坏字符数组bc和好字符数组suffix、prefix，分别计算两个策略的移动位数，取大值作为最终移动位数 int n = str.length; int m = pattern.length; int bc[ASCII_SIZE]; int* suffix = new int[m]; bool* prefix = new bool[m]; getBC(pattern, bc); getGS(pattern, suffix, prefix); int i = 0; while (i <= n - m) { int j = 0; for (j = m - 1; j >= 0; j--) { if (pattern.ch[j] != str.ch[i + j]) break; } if (j < 0) { delete suffix; delete prefix; return i; } else { int numBc = j - bc[(int)str.ch[i + j]]; int numGs = 0; if (j < m - 1) { numGs = getGSMove(suffix, prefix, m, j); } i += numBc > numGs ? numBc : numGs; } } delete suffix; delete prefix; return -1; } int main() { int n,m; cin>>n>>m; getchar(); HString ip[5000]; //ip数组存放n个ip地址 InputRule(ip,n); //输入n行规则，从规则中找到所有的ip地址，保存至ip数组中 HString log; log.ch=(char *)malloc(sizeof(char)*5000); strcpy(log.ch,""); //将log.ch初始化为空字符串 log.length=0; InputLog(log,m); //输入m行日志，将m行日志合并为1个长日志并保存至log中，返回长日志log的长度 for(int i=0;i { if(Index_BM(log,ip[i])!=-1) //返回值不为-1则匹配成功 { cout<<"Intrusion."< return 0; } } cout<<"No Intrusion."< return 0; } 05统计字符出现的频度 #include #include using namespace std; void Count(string c,int b[]) {//统计字符出现的频度 for(int i = 0; i < (int)c.length(); i++) { if(isdigit(c[i])) { b[(int)c[i] - 48]++; } else { b[(int)c[i] - 65 + 10]++; } } for(int i = 0; i < 36; i++) { if(b[i]) { if(i < 10) cout << i << ":" << b[i] << endl; if(i >= 10) { char c = (char)(i + 65 - 10); cout << c << ":" << b[i] << endl; } } } } int main() { string c; //存储输入的字符串 while(cin>>c) { if(c=="0") break; int *b=new int[36]{0}; //存储对应字符的个数 Count(c,b); } return 0; } 06递归实现字符串的逆序存储 #include #include #define MAXSIZE 100 using namespace std; void Reverse(char *a,int n) {//递归实现字符串的逆序存储 if((int)strlen(a) / 2 == n) return ; else { char t; t = a[n - 1]; a[n - 1] = a[(int)strlen(a) - n]; a[(int)strlen(a) - n] = t; Reverse(a, --n); } } int main() { char a[MAXSIZE]; while(cin>>a) { if(strcmp(a,"0")==0) break; int i=0; while(a[i]!='\0') i++; //统计字符数 Reverse(a,i); cout< } return 0; } 07字符串的插入 #include #define MAXSIZE 100 using namespace std; void Insert(char s[],char t[],int pos,int LenS,int LenT) {//字符串的插入 for(int i = LenS - 1 + LenT; i >= pos - 1 + LenT; i--) s[i] = s[i - LenT]; for(int i = pos - 1, j = 0; j < LenT; i++, j++) s[i] = t[j]; s[LenS + LenT] = '\0'; cout << s << endl; } int main() { int pos; while(cin>>pos) //输入插入位置pos { if(pos<=0) break; char s[MAXSIZE],t[MAXSIZE]; cin>>s>>t; //输入字符串s和t int LenS=0,LenT=0; while(s[LenS]!='\0') LenS++; //求字符串s的长度LenS while(t[LenT]!='\0') LenT++; //求字符串t的长度LenT if(pos>LenS) break; //插入位置非法 Insert(s,t,pos,LenS,LenT); } return 0; } 08查找子串第一次出现的位置 #include #include using namespace std; int strstr(string s1,string s2) {//查找子串第一次出现的位置 int i = 0, j = 0; while(i < (int)s1.length() && j < (int)s2.length()) { if(s1[i] == s2[j]) { i++; j++; } else { i = i - j + 1; j = 0; } } if(j >= (int)s2.length()) return i - s2.length(); else return -1; } using namespace std; int main() { string s1, s2; while(cin>>s1>>s2) { if (s1=="0"&&s2=="0") break; int pos=strstr(s1,s2); cout< } return 0; } 好文阅读
您阅读本篇文章共花了：
发表评论