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;
}

最新文章

  1. vmware centos nat模式下连不上网络解决办法
  2. ORACLE查出表所有的触发器及触发器详细信息
  3. 不挣扎了,开始学习LINQ TO XML,进而来解析网页。
  4. cong
  5. Windows phone 之自定义控件(补充)
  6. Java类加载的时机
  7. mogodb亿万级数据性能測试
  8. C#定义委托函数实现在别的窗体中操作主窗体中的SerialPort控件
  9. 矩形覆盖(JAVA)
  10. AutoCAD神器! AutoCAD自动切换中英文输入法插件(ZDSRF)
  11. laravel 路由缓存
  12. 饮冰三年-人工智能-Python-16Python基础之迭代器、生成器、装饰器
  13. 记录一次iptables端口转发的配置
  14. Codeforces 891C Envy
  15. 【转】Winform程序未捕获异常解决方法 EventType clr20r3 P1
  16. 原:android4.2.2蓝牙源码阅读--bluedroid部分
  17. linux下常用的几个时间函数:time,gettimeofday,clock_gettime,_ftime
  18. android之截屏(包括截取scrollview与listview的)
  19. Best Time to Buy and Sell Stock leetcode java
  20. Eclipse maven构建springmvc项目

热门文章

  1. JS的函数参数传递为值传递
  2. Html编码(&amp;#数字型)与解码小结 - 针对Puny Code(中文域名)的解码处理
  3. 如何让MVC和多层架构和谐并存(一)
  4. js 流程控制语句
  5. sql server 拆分字符串,拆分两次(:和;)
  6. UESTC 1246 拆x3
  7. python 3+djanjo 2.0.7简单学习(二)--创建数据库和模型
  8. Ubuntu搜狗输入法无法输入中文等问题
  9. burpsuite 出现 ssl_error_no_cypher_overlap
  10. ajaxfileup.js