Adament Cabin

  • 计算机
    • Algorithm
    • Linux
    • Problems
    • NEUQACM
  • 日语学习
  • ACG
    • 追番列表
    • 游戏
  • 常日说
  • 杂物
    • 资料
    • 资源
    • 治疗中心
  • ao的链接
  • 分站
  • Chinese
    • Japanese
Adament Cabin
恋厨综合症第二治疗中心
  1. 首页
  2. 计算机
  3. NEUQACM
  4. 正文

NEUQ-ACM实验班 W6

2021年11月23日 434点热度 0人点赞 0条评论

7-1

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

KMP(都写在标题里了)

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

Video1-bilibili

Video2-bilibili

#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,只包含大小写字母和数字)的哈希值:

  1. 不区分字母的大小写,沿用16进制A代表10,B代表11……的规律,将原字符串视为一串36进制的数字
  2. 将字符串平均划为4块,若无法平均划分,保证在前的分块不短于在后的分块,且长度差不超过1。如:长度26的字符串各分块长度为7、7、6、6,长度13的字符串各分块长度为4、3、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;
}
标签: C/C++/C#
最后更新:2022年10月15日

BiyiAdopac

是铁龙鸣。

点赞
< 上一篇
下一篇 >

文章评论

razz evil exclaim smile redface biggrin eek confused idea lol mad twisted rolleyes wink cool arrow neutral cry mrgreen drooling persevering
取消回复

文章目录
  • 7-1
  • 7-2
  • 7-3
分类
  • Algorithm / 5篇
  • Linux / 5篇
  • NEUQACM / 9篇
  • Problems / 3篇
  • 常日说 / 2篇
  • 日本語 / 2篇
  • 游戏 / 1篇
  • 计算机 / 22篇
  • 资料 / 4篇
标签聚合
Physics LaTex Arcaea ArchLinux Magisk Learning C/C++/C#
ヤツメ穴
https://www.adament.xyz/wp-content/uploads/2022/03/ヤツメ穴(BGM).mp3
クリスタルグラビティ
https://www.adament.xyz/wp-content/uploads/2022/08/CrystalGravity.mp3

COPYRIGHT © 2022 adament.xyz. ALL RIGHTS RESERVED.
本站虽然不重要但是还是有的 隐私政策