7-1

给定一个字符串 text 和一个模式串 pattern，求 pattern 在text 中的出现次数。text 和 pattern 中的字符均为英语大写字母或小写字母。text中不同位置出现的pattern 可重叠。

KMP（都写在标题里了）

下面两个视频帮助了我很多。

#include <iostream>
#include <string>
#include <vector>
using namespace std;
string pattern,text;
int findcatch=0;
int backvalue[100005];
void getbackvaluetable(string pattern){
    int ins = 0;
    for (int i = 1; i < pattern.size(); i++){
        if (pattern[i] == pattern[ins]){
            ins++;
            backvalue[i] = ins;
        }
        else{
            if (ins > 1)
                ins = backvalue[ins - 1];
            backvalue[i] = ins;
        }
    }
}
void movetable(int n){
    for(int i=n;i>0;i--){
        backvalue[i]=backvalue[i-1];
    }
    backvalue[0]=-1;
}
void kmpsearch(string pattern,string text){
    getbackvaluetable(pattern);
    movetable(pattern.size());
    int i=0,j=0;
    while(i<text.size()){
        if(j==pattern.size()-1&&text[i]==pattern[j]){
            findcatch++;
            j=backvalue[j];
        }
        if(text[i]==pattern[j]){
            i++;j++;
        }
        else{
            j=backvalue[j];
            if(j==-1){
                i++;j++;
            }
        }
    }
}
int main(){
    cin >> text;
    cin >> pattern;
    kmpsearch(pattern,text);
    cout << findcatch << endl;
    return 0;
}

7-2

众所周知，互联网时代以来各大公司被“脱裤”的历史是一部五彩缤纷（误）的血泪史，给各大厂商造成了极大的经济损失。更为重要的是，由于有些用户在多个网站使用相同的用户名、密码，一旦一家网站被拖库，用户往往会遭受全方位的损失。为避免此情况，良心企业一般只在数据库中存储用户密码的哈希值——也就是根据特定规则产生的散列值，无法由此倒推出原密码。但这种方法也有一个缺点，即输入不同的密码有极小概率会得到一样的哈希值（我们称之为碰撞），从而被系统认定密码正确！现在你所在的公司采取如下方法产生密码字符串（长度至少为8，只包含大小写字母和数字）的哈希值：

不区分字母的大小写，沿用16进制A代表10，B代表11……的规律，将原字符串视为一串36进制的数字

将字符串平均划为4块，若无法平均划分，保证在前的分块不短于在后的分块，且长度差不超过1。如：长度26的字符串各分块长度为7、7、6、6，长度13的字符串各分块长度为4、3、3、3

将每块的数字加和，取其个位数，四块取出的四个36进制数字顺次连接，得到一个四位36进制数字，即为该密码字符串的哈希值。
然而由于这种方式过于睿智，使得碰撞的几率奇高，你的任务就是为公司防范风险，在碰撞发生的时候给予示警！

这道题按照题目要求一步一步来即可。

首先要将密码打碎成三部分

void breakstring(int n){//分成4部分的各部分长度
  s1=s2=s3=s4=n/4;
  n=n-s1*4;
  if(n>0) {s1++;n--;}
  if(n>0) {s2++;n--;}
  if(n>0) {s3++;n--;}
  return;
}

再把一个字符转化为36进制（我这种方法过于麻烦）

int turn10(char n){
  if(n>='0'&&n<='9') return (int)(n-'0');
  else if(n>='a'&&n<='z') return (int)(n-'a')+10;
  else if(n>='A'&&n<='Z') return (int)(n-'A')+10;
}
char turn36(int n){
  if(n>=0&&n<=9) return (char)(n+'0');
  else if(n>=10&&n<=35) return (char)(n-10+'a');
  else return turn36(n-36);
}

通过上面两个（三个）函数计算一串字符的哈希。

string Hashing(string str){
    string num="0000";
    int bnum=0;
    if(str.size()<=4) return str;
    breakstring(str.size());
    int i=0;
    for(i=0;i<s1;i++){
        bnum+=turn10(str[i]);
    }
    num[0]=turn36(bnum);
    bnum=0;
    for(;i<s1+s2;i++){
        bnum+=turn10(str[i]);
    }
    num[1]=turn36(bnum);
    bnum=0;
    for(;i<s1+s2+s3;i++){
        bnum+=turn10(str[i]);
    }
    num[2]=turn36(bnum);
    bnum=0;
    for(;i<str.size();i++){
        bnum+=turn10(str[i]);
    }
    num[3]=turn36(bnum);
    return num;
}

最后再做主程序即可。

下面是我极为复杂的代码。

#include <iostream>
#include <cstring>
#include <vector>
using namespace std;
int s1,s2,s3,s4;
struct users{
  string name;
  string passwd;
  string hash;
};
vector<users> usersdata;
void breakstring(int n){
  s1=s2=s3=s4=n/4;
  n=n-s1*4;
  if(n>0) {s1++;n--;}
  if(n>0) {s2++;n--;}
  if(n>0) {s3++;n--;}
  return;
}
int turn10(char n){
  if(n>='0'&&n<='9') return (int)(n-'0');
  else if(n>='a'&&n<='z') return (int)(n-'a')+10;
  else if(n>='A'&&n<='Z') return (int)(n-'A')+10;
}
char turn36(int n){
  if(n>=0&&n<=9) return (char)(n+'0');
  else if(n>=10&&n<=35) return (char)(n-10+'a');
  else return turn36(n-36);
}
string Hashing(string str){
  string num="0000";
  int bnum=0;
  if(str.size()<=4) return str;
  breakstring(str.size());
  int i=0;
  for(i=0;i<s1;i++){
      bnum+=turn10(str[i]);
  }
  num[0]=turn36(bnum);
  bnum=0;
  for(;i<s1+s2;i++){
      bnum+=turn10(str[i]);
  }
  num[1]=turn36(bnum);
  bnum=0;
  for(;i<s1+s2+s3;i++){
      bnum+=turn10(str[i]);
  }
  num[2]=turn36(bnum);
  bnum=0;
  for(;i<str.size();i++){
      bnum+=turn10(str[i]);
  }
  num[3]=turn36(bnum);
  return num;
}
int main(){
/*     
  string str;
  cin >> str;
  cout << Hashing(str) << endl;
   */
  int abc;
  cin >> abc;
  char operation;
  string name,password;
  bool repeated;
  for(int i=1;i<=abc;i++){
      cin >> operation;
      repeated=false;
      if(operation=='R'){
          cin >> name >> password;
          for(int i=0;i<usersdata.size();i++){
              if(name==usersdata[i].name){
                  cout << "Repeated!" << endl;
                  repeated=true;
                  break;
              }
          }
          if(!repeated){
              users newuser;
              newuser.name=name;
              newuser.passwd=password;
              newuser.hash=Hashing(password);
              usersdata.push_back(newuser);
              cout << "Signed!" << endl;
          }
      }
      if(operation=='L'){
          cin >> name >> password;
          users compareduser;
          for(int i=0;i<usersdata.size();i++){
              if(name==usersdata[i].name){
                  compareduser=usersdata[i];
                  break;
              }
          }
          if(password==compareduser.passwd){
              cout << "Success!" << endl;
          }
          else{
              if(Hashing(password)==compareduser.hash) cout << "Attention!" << endl;
              else cout << "Failed!" << endl;
          }
      }
  }
  return 0;
}

7-3

分别输入两个字符串A和B，A由多个小字符串组成（中间由非字母隔开），B是由字母组成的字符串。求出A中包含B的小字符串的个数（详细看样例），并且输出它。（不区分大小写）

这也是一个KPM，直接照抄7-1，唯一的改动就是要把一串字符串给打碎分出来。

while(true){
    ch=getchar();
    if(ch=='n') {if(!stra.empty())stras.push_back(stra);break;}
    else if(ch>='a'&&ch<='z'){
        stra+=ch;
    }else if(ch>='A'&&ch<='Z'){
        stra+=ch+32;
    }else{
        if(!stra.empty())stras.push_back(stra);
        stra.clear();
    }
}

#include <iostream>
#include <cstring>
#include <vector>
using namespace std;
vector<string>stras;
int backvalue[100005];
void backvaluetable(string pattern){
    int ins = 0;
    for (int i = 1; i < pattern.size(); i++){
        if (pattern[i] == pattern[ins]){
            ins++;
            backvalue[i] = ins;
        }
        else{
            if (ins > 1)
                ins = backvalue[ins - 1];
            backvalue[i] = ins;
        }
    }
    for(int i=pattern.size();i>0;i--){
        backvalue[i]=backvalue[i-1];
    }
    backvalue[0]=-1;
}
int kmpsearch(string pattern,string text){
    int i=0,j=0;
    while(i<text.size()){
        if(j==pattern.size()-1&&text[i]==pattern[j]){
            return 1;
        }
        if(text[i]==pattern[j]){
            i++;j++;
        }
        else{
            j=backvalue[j];
            if(j==-1){
                i++;j++;
            }
        }
    }
    return 0;
}
int main(){
    char ch;
    string stra;
    string strb;
    while(true){
        ch=getchar();
        if(ch=='n') {if(!stra.empty())stras.push_back(stra);break;}
        else if(ch>='a'&&ch<='z'){
            stra+=ch;
        }else if(ch>='A'&&ch<='Z'){
            stra+=ch+32;
        }else{
            if(!stra.empty())stras.push_back(stra);
            stra.clear();
        }
    }
    cin>>strb;
    backvaluetable(strb);
    for(int i=0;i<strb.size();i++){
        if(strb[i]>='A'&&strb[i]<='Z') strb[i]+=32;
    }
    int sum=0;
    for(int i=0;i<stras.size();i++){
        sum+=kmpsearch(strb,stras[i]);
    }
    cout << sum << endl;
    return 0;
}

NEUQ-ACM实验班 W6

7-1

7-2

7-3

文章评论