当前位置:网站首页>Input two strings and output the longest substring with the same length
Input two strings and output the longest substring with the same length
2022-06-22 19:30:00 【Douglas_ LT】
#pragma warning(disable :4996)
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include <stdio.h>
#include<string>
#include<vector>
#include<algorithm>
#include<map>
using namespace std;
typedef long long LL;
const LL MOD = 1000000007;
const LL P = 1000009;
const LL MAXN = 1010;
LL powP[MAXN] = {
0 }, H1[MAXN] = {
0 }, H2[MAXN] = {
0 };
vector<pair<int, pair<int, int>>> pr1, pr2;
void init(int len)
{
powP[0] = 1;
for (int i = 1; i < len; i++)
{
powP[i] = (powP[i - 1] * P) % MOD;
}
}
void calH(LL H[],string str)
{
H[0] = str[0];
for (int i = 0; i < str.length(); i++)
{
H[i] = (H[i - 1] * P + str[i]) % MOD;
}
}
LL calSingleSubH(LL H[],int i,int j)
{
if (i == 0)
{
return H[j];
}
else
{
return abs(H[j] - H[i - 1] * powP[j - i + 1]) % MOD;
}
}
void calSubH(LL H[], int len,vector<pair<int, pair<int, int>>>& pr)
{
for (int i = 0; i < len; i++)
{
for (int j = 1; j < len; j++)
{
int hashvalue = calSingleSubH(H, i, j);
pr.push_back(make_pair(hashvalue,make_pair(i,j)));
}
}
}
int beginn=0, endd=0;
void getmax()
{
pair<int, int>p;
int ans = 0;
for (int i = 0; i < pr1.size(); i++)
{
for (int j = 0; j < pr2.size(); j++)
{
if (pr1[i].first == pr2[j].first)
{
p=pr1[i].second;
int temp1 = p.first,temp2=p.second;
if (temp2 - temp1 > ans)
{
ans = temp2 - temp1;
beginn = temp1;
endd = temp2;
}
}
}
}
}
int main()
{
string s1, s2;
cin >> s1 >> s2;
int len1 = s1.length(), len2 = s2.length();
init(max(len1, len2));
calH(H1, s1);
calH(H2, s2);
calSubH(H1, len1, pr1);
calSubH(H2, len2, pr2);
getmax();
for (int i = beginn; i <= endd; i++)
{
cout << s1[i];
}
return 0;
}
边栏推荐
- 使能伙伴,春节重大保障“不停歇”
- Interview MySQL
- 5g short message solution
- 200亿VS 50亿,“脱水”小红书,到底值多钱?
- Makefile将某一部分文件不编译
- SSH password free login
- Error in created hook: “TypeError: Cannot read property ‘tableId‘ of undefined“
- 同花顺好用么?手机开户安全么?
- 远程访问及控制——SSH远程管理及TCP Wrappers 访问控制
- Problems of different renderers running on the web with flutter2.0
猜你喜欢

In the first half of the year, there were 7 new unicorns in this field, and the capital scrambled to enter the market

JVM quick start

Digital business cloud: build a digital supply chain system to enable enterprises to optimize and upgrade their logistics supply chain

Shell编程规范与变量

第八届 GopherChina 大会蓄势待发!

Typescript (7) generic

常用技术注解

Detailed explanation of shell script (x) -- how to use sed editor

线程池:ThreadPoolExcutor源码阅读

小波变换db4进行四层分解及其信号重构—matlab分析及C语言实现
随机推荐
shell脚本(五)——函数
Cluster, distributed and microservice concepts and differences
缓存3种方式及原理
Makefile does not compile some files
5g short message solution
wpa_ CLI parameter description
5GC和卫星融合通信方案
How to manage tasks in note taking software such as flowus and notation?
Typescript (7) generic
STM32控制矩阵按键,HAL库,cubeMX配置
Digital enabling machinery manufacturing industry, supply chain collaborative management system solution helps enterprises upgrade their supply chain
同花顺好用么?手机开户安全么?
Flutter系列-Dart基础语法学习
ssh免密码登录
贪心之分配问题(2)
牛客网:最小覆盖子串
wpa_ State machine migration of supplicant
数字赋能机械制造业,供应链协同管理系统解决方案助力企业供应链再升级
Activity跳转到Fragment的方法(Intent)
加工制造业智慧采购系统解决方案:助力企业实现全流程采购一体化协同