二维KMP-OpenJudge-挤奶网格

谁践踏了优雅 2022-05-15 12:13 181阅读 0赞

*  # 二维KMP-OpenJudge-挤奶网格 #

--------------------

*  ## 题目链接： ##

[挤奶网格][Link 1]

*  ## 思路： ##

### 题目大意： ###

给一个二维字符串数组，求能覆盖得到该数组的最小面积

### 题解： ###

**求最小覆盖面积，类似一维KMP求最长覆盖串（Len-Next【Len】）**

**对原字符矩阵每一行进行KMP，求出行的覆盖度**

**转置后求列覆盖度**

覆盖度=Len-Next\[Len\]

***覆盖度乘积为所求***

*  ## 代码： ##

#include<iostream>
    #include<cstring>
    
    /*
    1.把每行字符串看作一个整体对行求next数组
    2.将矩阵转置
    3.进行操作1，注意这里的行是原来的列，列是原来的行，相当于求原来列的next数组
    4.求出len－next[len]即最小不重复子串的长度作为子矩形的边长
    */
    using namespace std;
    #define MAX_ROW 10005
    #define MAX_COL 80
    
    char COW[MAX_ROW][MAX_COL];
    char Transpose_COW[MAX_COL][MAX_ROW];
    
    int Next_ROW[MAX_ROW];
    int Next_COL[MAX_ROW];
    
    int ROW, COL;
    
    void Get_NextR()					//求行
    {
    	int j = -1, k = 0;
    	Next_ROW[0] = -1;
    	while (k < ROW)
    	{
    		if (j == -1 || !strcmp(COW[j], COW[k]))
    		{
    			j++;
    			k++;
    			Next_ROW[k] = j;
    		}
    		else
    			j = Next_ROW[j];
    	}
    }
    
    void Get_NextC()
    {
    	int j = -1, k = 0;
    	Next_COL[0] = -1;
    	while (k < COL)
    	{
    		if (j == -1 || !strcmp(Transpose_COW[j], Transpose_COW[k]))
    		{
    			j++;
    			k++;
    			Next_COL[k] = j;
    		}
    		else
    			j = Next_COL[j];
    	}
    }
    
    
    int main()
    {
    	while (cin >> ROW >> COL)
    	{
    		for (int i = 0; i < ROW; i++)
    			cin >> COW[i];
    		Get_NextR();
    		for (int i = 0; i < ROW; i++)
    			for (int j = 0; j < COL; j++)
    				Transpose_COW[j][i] = COW[i][j];
    		Get_NextC();
    		
    		int MIN_CoverNet = (ROW - Next_ROW[ROW])*(COL - Next_COL[COL]);
    
    		cout << MIN_CoverNet << endl;
    	}
    	return 0;
    }

[Link 1]: http://dsalgo.openjudge.cn/string/10/