[Codeforces958A2]Death Stars (medium)(字符串+hash)
2024-09-08 13:10:42
Description
Solution
这里用类似hash的方法将判断2个矩阵是否相同的时间降为O(m),总时间复杂度为O(m3)
Code
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std; const int mo=997;
int n,m,AA[2010],BB[210][2010];
char A[2010][210],B[210][2010],tmp[210][210]; int main(){
scanf("%d%d\n",&n,&m);
for(int i=1;i<=n;++i){
scanf("%s\n",A[i]+1);
for(int j=1;j<=m;++j) AA[i]=(AA[i]+(A[i][j]-97+1)*j)%mo;
}
for(int i=1;i<=m;++i){
scanf("%s\n",B[i]+1);
for(int j=1;j+m-1<=n;++j){
int r=j+m-1;
for(int k=j,kk=1;k<=r;++k,++kk) BB[i][j]=(BB[i][j]+(B[i][k]-97+1)*kk)%mo;
}
}
for(int q=1;q+m-1<=n;++q)
for(int g=1;g+m-1<=n;++g){
bool b=1;int tmp=0;
for(int i=1,j=q;i<=m;++i,++j) if(AA[j]!=BB[i][g]){b=0;break;}
if(b){
printf("%d %d\n",q,g);
return 0;
} }
return 0;
}
最新文章
- vmware centos nat模式下连不上网络解决办法
- ORACLE查出表所有的触发器及触发器详细信息
- 不挣扎了,开始学习LINQ TO XML,进而来解析网页。
- cong
- Windows phone 之自定义控件(补充)
- Java类加载的时机
- mogodb亿万级数据性能測试
- C#定义委托函数实现在别的窗体中操作主窗体中的SerialPort控件
- 矩形覆盖(JAVA)
- AutoCAD神器! AutoCAD自动切换中英文输入法插件(ZDSRF)
- laravel 路由缓存
- 饮冰三年-人工智能-Python-16Python基础之迭代器、生成器、装饰器
- 记录一次iptables端口转发的配置
- Codeforces 891C Envy
- 【转】Winform程序未捕获异常解决方法 EventType clr20r3 P1
- 原:android4.2.2蓝牙源码阅读--bluedroid部分
- linux下常用的几个时间函数:time,gettimeofday,clock_gettime,_ftime
- android之截屏(包括截取scrollview与listview的)
- Best Time to Buy and Sell Stock leetcode java
- Eclipse maven构建springmvc项目
热门文章
- JS的函数参数传递为值传递
- Html编码(&;#数字型)与解码小结 - 针对Puny Code(中文域名)的解码处理
- 如何让MVC和多层架构和谐并存(一)
- js 流程控制语句
- sql server 拆分字符串,拆分两次(:和;)
- UESTC 1246 拆x3
- python 3+djanjo 2.0.7简单学习(二)--创建数据库和模型
- Ubuntu搜狗输入法无法输入中文等问题
- burpsuite 出现 ssl_error_no_cypher_overlap
- ajaxfileup.js