POJ-2185-Milking Grid

ACM模版

描述

题解

image.png

代码

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

const int MAXN = 1e4 + 10;
const int MAXM = 100;

int r, c, R, C;
int nxt[MAXN];
int cnt[MAXM];
char a[MAXM];
char s[MAXN][MAXM];

int main(int argc, const char * argv[])
{
    memset(cnt, 0, sizeof(cnt));

    scanf("%d%d", &r, &c);

    for (int i = 0; i < r; i++)
    {
        scanf("%s", s[i]);
        strcpy(a, s[i]);

        for (int j = c - 1; j > 0; j--)
        {
            a[j] = 0;
            int x = 0, y = 0;
            for (; s[i][y]; x++, y++)
            {
                if (!a[x])
                {
                    x = 0;
                }
                if (a[x] != s[i][y])
                {
                    break;
                }
            }
            if (!s[i][y])
            {
                cnt[j]++;
            }
        }
    }

    for (int i = 0; i < c; i++)
    {
        if (cnt[i] == r)
        {
            C = i;
            break;
        }
    }

    for (int i = 0; i < r; i++)
    {
        s[i][C] = 0;
    }

    nxt[0] = -1;
    for (int i = 1, j = -1; i < r; i++)
    {
        while (j != -1 && strcmp(s[j + 1], s[i]))
        {
            j = nxt[j];
        }

        if (!strcmp(s[j + 1], s[i]))
        {
            j++;
        }
        nxt[i] = j;
    }
    R = r - nxt[r - 1] - 1;

    printf("%d\n", R * C);

    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 51Nod-1612-合法表达式

    ACM模版 描述 ? 题解 我们需要考虑到能够加多少括号以及加括号的动态规划过程,这里格外要注意一个问题,就是初始字符串不合法,并且无论怎么加都不合法的情况,比...

    f_zyj
  • HDU-5584-LCM Walk

    ACM模版 描述 ? 题解 image.png 代码 #include <iostream> using namespace std; int gcd(in...

    f_zyj
  • 51Nod-1203-JZPLCM

    ACM模版 描述 ? 题解 这个题的解法好像好多好多,可以线段树解,自然也可以用树状数组解,还有大佬直接莫队推过,我这里用的树状数组搞得。 首先将数进行拆解,拆...

    f_zyj
  • loj#6031. 「雅礼集训 2017 Day1」字符串(SAM 广义SAM 数据分治)

    考虑K比较小的情况,可以直接暴力建SAM, 枚举w的子串算出现次数。询问用个 的vector记录一下每次在vector里二分就好。

    attack
  • 桶排序

    3. 桶排序        桶排序的思想是若待排序的记录的关键字在一个明显有限范围内(整型)时,可设计有限个有序桶,每个桶装入一个值(当然也可以装入若干个值),...

    attack
  • Search Insert Position

    问题:一个数应该插入到有序数组的哪个位置 class Solution { public: int searchInsert(int A[], int ...

    用户1624346
  • 长沙理工新生赛

    https://ac.nowcoder.com/acm/contest/3530/A

    AngelNH
  • HDU 6401 Magic Square 模拟

    用户2965768
  • Codeforces Global Round 2 C. Ramesses and Corner Inversion(思维)

    版权声明:欢迎转载,若转载,请标明出处,如有错误,请指点,也欢迎大佬们给出优化方法 https://blog.csdn.net/Charles_Zaqd...

    Ch_Zaqdt
  • 洛谷P4723 【模板】线性递推(多项式取模 线性代数)

    attack

扫码关注云+社区

领取腾讯云代金券