POJ 2185 Milking Grid [二维KMP next数组]
直接转田神的了:
Time Limit: 3000MS | Memory Limit: 65536K | |
Total Submissions: 6665 | Accepted: 2824 |
Description
Help FJ find the rectangular unit of smallest area that can be repetitively tiled to make up the entire milking grid. Note that the dimensions of the small rectangular unit do not necessarily need to divide evenly the dimensions of the entire milking grid, as indicated in the sample input below.
Input
* Lines 2..R+1: The grid that the cows form, with an uppercase letter denoting each cow's breed. Each of the R input lines has C characters with no space or other intervening character.
Output
Sample Input
2 5
ABABA
ABABA
Sample Output
2
Hint
Source
题目链接:http://poj.org/problem?id=2185
题目大意:给你一个r行c列的字符矩阵,令其一个子矩阵,使得这个子矩阵无限复制成的大矩阵包含原矩阵,现求这个子矩阵的最小尺寸
题目分析:1.把每行字符串看作一个整体对行求next数组
2.将矩阵转置
3.进行操作1,注意这里的行是原来的列,列是原来的行,相当于求原来列的next数组
4.求出len-next[len]即最小不重复子串的长度作为子矩形的边长
13892851 | njczy2010 | 2185 | Accepted | 42452K | 79MS | G++ | 1707B | 2015-02-16 10:51:05 |
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#include<stack>
#include<string> #define N 100
#define M 10005
//#define mod 10000007
//#define p 10000007
#define mod2 1000000000
#define ll long long
#define LL long long
#define eps 1e-6
//#define inf 2147483647
#define maxi(a,b) (a)>(b)? (a) : (b)
#define mini(a,b) (a)<(b)? (a) : (b) using namespace std; int n,m;
char s[M][M];
char c[M][M];
int nexts[M];
int nextc[M];
int l;
int now; void get_nexts()
{
int i,j;
i=;j=-;nexts[]=-;
while(i<n)
{
if(j==- || strcmp(s[i],s[j])==){
i++;j++;nexts[i]=j;
}
else{
j=nexts[j];
}
}
} void get_nextc()
{
int i,j;
i=;j=-;nextc[]=-;
while(i<m)
{
if(j==- || strcmp(c[i],c[j])==){
i++;j++;nextc[i]=j;
}
else{
j=nextc[j];
}
}
} void ini()
{
int i,j;
for(i=;i<n;i++){
scanf("%s",s[i]);
}
for(j=;j<m;j++){
for(i=;i<n;i++){
c[j][i]=s[i][j];
}
c[j][i]='\0';
}
} void solve()
{
get_nexts();
get_nextc();
} void out()
{
printf("%d\n",(n-nexts[n])*(m-nextc[m]));
} int main()
{
//freopen("data.in","r",stdin);
//freopen("data.out","w",stdout);
//scanf("%d",&T);
//for(int ccnt=1;ccnt<=T;ccnt++)
//while(T--)
//scanf("%d%d",&n,&m);
while(scanf("%d%d",&n,&m)!=EOF)
{
ini();
solve();
out();
}
return ;
}
最新文章
- 跨站脚本攻击XSS
- 原生js实现简洁的返回顶部组件
- excel公式处理成绩表
- msi软件包无法安装
- js 删除效果代码
- http验证CertificateValidation
- 包含常用功能的 gulpfile.js
- JQEUI问题收集
- vue.js实战——$event
- ecplise多个版本tomcat的使用
- vue axios上传文件实例
- 基本数据类型补充,深浅copy
- MVVM 简介
- openshift 容器云从入门到崩溃之五《部署应用》
- Java面向对象 第2节 Scanner 类和格式化输出printf
- 微信小程序 封装请求
- 解决win10系统dpi放大后,部分网页文字颜色很浅的问题
- 给VMware下的Linux扩展磁盘空间(以CentOS6.3为例)
- 如何生成安全的密码 Hash:MD5, SHA, PBKDF2, BCrypt 示例
- 情感分析snownlp包部分核心代码理解
热门文章
- WPF知识点全攻略02- WPF体系结构
- shell脚本,awk 匹配的做修改后打印,不匹配的打印。
- ratio_to_report分析函数求占比
- Zookeeper 集群 BindException: Cannot assign requested address 解决方案
- tkinter学习-滚动条
- 搭建pip源
- RN与现有的原生app集成
- PyQt5(1)——QToolTip, QPushButton, QMessageBox, QDesktopWidget
- python中实现格式化输出 %用法
- [学习笔记]一个实例理解Lingo的灵敏性分析