首页 > 编程语言 >编程一小时2023.5.12

编程一小时2023.5.12

时间:2023-05-12 22:11:22浏览次数:49  
标签:12 return int 编程 rev right 2023.5 base left

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <unordered_set>
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#define l first
#define r second

using namespace std;
typedef pair<int, int> PII;

string s1, s2;
vector<PII> intervals; 

typedef unsigned long long ULL;

const int N = 1e4 + 10;
int n, m;

class StringHash {
public:
explicit StringHash(string& str, int base=131) {
n = str.size();
this->base = base;
string s = "*" + str;
p[0] = 1;
for(int i = 1; i <= n; i++){
h[i] = h[i - 1]*base + s[i];
p[i] = p[i - 1]*base;
}
for(int i = n; i >= 1; i--) {
rev_h[i] = rev_h[i + 1]*base + s[i];
}
}

bool is_palindrome(int left, int right){
if(left > right) return true;
return shash(left, right) == shash(left, right, true);
}

vector<int> find(string& t) {
int m = t.size();
vector<int> pos;
if(m > n) return pos;
t = "*" + t;
ULL ht[N], pt[N];
pt[0] = 1;
for(int i = 1; i <= m; i++){
ht[i] = ht[i - 1]*base + t[i];
pt[i] = pt[i - 1]*base;
}
ULL h2 = ht[m] - ht[0]*pt[m];
for(int i = 1; i <= n - m + 1; i++) {
ULL h1 = shash(i, i + m - 1);
if(h1 == h2) pos.push_back(i - 1);
}
return pos;
}

ULL shash(int left, int right, bool is_rev=false) {
++left, ++right;
return is_rev? rev_h[left] - rev_h[right + 1]*p[right - left + 1]: h[right] - h[left - 1]*p[right - left + 1];
}

private:
int base, n;
ULL h[N], rev_h[N], p[N];
};

bool check(StringHash& sh1, StringHash& sh2, int len) {
unordered_set<ULL> us;
for(int l = 0; l + len - 1 < m; l++) {
int r = l + len - 1;
us.insert(sh2.shash(l, r));
}
for(auto&range: intervals) {
for(int l = range.l; l + len - 1 <= range.r; l++) {
int r = l + len - 1;
ULL hash_val = sh1.shash(l, r);
if(us.find(hash_val) != us.end()) return true;
}
}
return false;
}

int main() {
cin >> s1 >> s2;
n = s1.size(), m = s2.size();
int i = 0;
while(i < n && isdigit(s1[i])) i++;
while(i < n) {
int j = i;
while(j < n) {
if(j < n - 1) {
if(isalpha(s1[j + 1])) j++;
else break;
}else {
break;
}
}
if(j < n) {
intervals.push_back({i, j});
i = j + 1;
while(i < n && isdigit(s1[i])) i++;
}else {
break;
}
}
StringHash stringhash1(s1), stringhash2(s2);
int left = 0, right = min(n, m);
while(left < right) {
int mid = left + right + 1 >> 1;
if(check(stringhash1, stringhash2, mid)) {
left = mid;
}else {
right = mid - 1;
}
}
printf("%d", right);
return 0;
}

 

标签:12,return,int,编程,rev,right,2023.5,base,left
From: https://www.cnblogs.com/zbl040721/p/17396404.html

相关文章

  • 2023-05-12:存在一个由 n 个节点组成的无向连通图,图中的节点按从 0 到 n - 1 编号, 给你
    2023-05-12:存在一个由n个节点组成的无向连通图,图中的节点按从0到n-1编号,给你一个数组graph表示这个图,其中,graph[i]是一个列表,由所有与节点i直接相连的节点组成。返回能够访问所有节点的最短路径的长度。你可以在任一节点开始和停止,也可以多次重访节点,并且可以重......
  • 每日总结-23.5.12
    <%HttpSessionhttpSession=request.getSession();//Stringtea_id=(String)httpSession.getAttribute("id_");Stringtea_id=request.getParameter("id_");Thesqlthesql=newThesql();request.setCharacterEncoding(......
  • python软件与编程语言
    编程语言的发展史1.机器语言:计算机内部只认识01二进制数据  #由于计算机是基于电工作的,电是有高低电频之分的,高电频和低电频 优点:执行速度快 缺点:学习难度大2.汇编语言  #用简单的字母表示一串二进制  00011001  a  00001  b  00010  c......
  • 2023.5.12每日总结
    packageshiyan;importjava.sql.*;importjava.text.ParseException;importjava.text.SimpleDateFormat;importjava.util.Date;publicclassAllMethods{publicConnectionconnect;publicAllMethods()throwsException{Class.forName(&q......
  • 5.12每日总结
    <%@pagelanguage="java"contentType="text/html;charset=UTF-8"pageEncoding="UTF-8"%><!DOCTYPEhtmlPUBLIC"-//W3C//DTDHTML4.01Transitional//EN""http://www.w3.org/TR/html4/loose.dtd&qu......
  • 每日总结 5.12
    今日进行了web实验。对于之前所学习的增删改查进行熟练学习。1)    开MySQL,新建一个数据库。2)    新建一个数据库表。3)    在表中增加若干记录,作为初始数据。4)    打开Eclipse软件,新建一个名为Lab03的Web项目,并设置其部署程序为Tomcat。5)    在......
  • 每日总结2023-05-12
    今天完成了dialog的简易模式:privatevoidshowQieDialog(){AlertDialog.Builderbuilder=newAlertDialog.Builder(this);builder.setTitle("切换账号提示").setMessage("请确认切换账号").setPositiveButton("......
  • C++趣味编程
    最佳存款方案1#include<iostream>2usingnamespacestd;3intmain()4{5doublex=1000;6for(inti=1;i<=5;i++)7{8x=x/(1+12*0.0063);9if(i!=5)10{11x=x+1000;12}13}14......
  • WLED and WS2812B RGB LEDs Strip All In One
    WLEDandWS2812BRGBLEDsStripAllInOneWLEDAppWLEDControlWS2812BandmanymoretypesofdigitalRGBLEDswithanESP8266orESP32overWi-Fi!https://github.com/Aircoookie/WLEDhttps://kno.wled.ge/Wi-Fihttps://en.wikipedia.org/wiki/Wi-FiH......
  • 5.12每日总结
    今天学习了nextInt、nextFloat、nextDoublenext():用于读取String字符串数组,以空格划分(只读取输入直到空格),在读取后将光标指向本行nextLine():用于读取String字符串数组,读取包括单词之间的空格和除回车以外的所有符号,在读取后将光标指向下一行publicstaticvoidmain(String[]arg......