(字符串的模式匹配4.7.18)POJ 1961 Period(求一个串到第i个字符循环节出现的次数)...

小灰灰 2022-05-12 22:36 125阅读 0赞

/*
     * POJ_1961.cpp
     *
     *  Created on: 2013年10月29日
     *      Author: Administrator
     */
    
    #include <iostream>
    #include <cstdio>
    #include <cstring>
    
    const int maxn = 1000005;//在IDE测试时可能会报错,因为可能它开不了那么大的数组,这是需要把maxn调小一点来进行测试
    
    int main() {
    	int n;
    	int counter = 1;
    	while (scanf("%d", &n) != EOF, n) {
    		char str[maxn];
    		scanf("%s", str);
    
    		int len = strlen(str);
    
    		int suffix[maxn + 1];
    
    		//应用KMP算法计算单词w的前缀函数
    		suffix[0] = -1;
    		suffix[1] = 0;
    		int cur, p = 0;
    		for (cur = 2; cur <= len; ++cur) {
    			while (p >= 0 && str[p] != str[cur - 1]) {
    				p = suffix[p];
    			}
    
    			suffix[cur] = ++p;
    		}
    
    		if(counter != 1){
    			printf("\n");
    		}
    		printf("Test case #%d\n",counter++);
    		int i;
    		/**
    		 * POJ_2406 :其实求的是整个串的循环节数,而
    		 * POJ_1961 :求的是一个串到第i个字符时所出现的循环节数...也就是多了一个循环而已
    		 *
    		 */
    		for (i = 1; i <= n; ++i) {
    			//如果len是(len - suffix[len])的前缀,即,假如当前的重复串的长度能被原串的长度整除...
    			if ((i % (i - suffix[i])) == 0 &&(i / (i - suffix[i])>1)) {
    				printf("%d %d\n", i ,(i / (i - suffix[i])));
    			}
    		}
    	}
    
    	return 0;
    
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，125人围观）

还没有评论，来说两句吧...

相关阅读

相关 LA 3026 && POJ 1961 Period （利用kmp中的next数组找最大的循环节）

周期（ Period, SEERC 2004, LA3026）给定一个长度为n的字符串S，求它每个前缀的最短循环节。换句话说，对于每个i（ 2≤i≤n），

浅浅的花香味﹌/ 2024年02月17日 22:20/ 0 赞/ 14 阅读

相关求一个字符串中连续出现最多的子串次数

时间：2014.09.12 地点：基地心情：明天就要和欧阳去武汉面试阿里了，整理一下同学求助的一道题，写下这一篇，愿一切顺利。一、题目：求一个字符串中连续出现

拼搏现实的明天。/ 2022年08月12日 01:10/ 0 赞/ 168 阅读

相关求一个字符串中连续出现的次数最多的子串

求一个字符串中连续出现的次数最多的子串。例如字符串“abababc”,最多连续出现的为ab，连续出现三次。要和求一个字符串中的最长重复子串区分开来，还是上面的字符串，那么最长的

布满荆棘的人生/ 2022年08月03日 05:26/ 0 赞/ 216 阅读

相关字符串中的快速模式匹配2

字符串中的快速模式匹配2 2、算法程序模式匹配过程的一般形式： > > 将模式置于最左边； > > > > while 模式没有完全匹配and文本没有读完do

悠悠/ 2022年06月16日 09:20/ 0 赞/ 146 阅读

相关字符串中的快速模式匹配1

字符串中的快速模式匹配1 1、非正式推演：如果我们想象着以某种方法把模式从文本的左边滑动至文本的最右面，那么本文讲的模式匹配方法可能就会很容易掌握了。举个例子，在

小咪咪/ 2022年06月16日 07:19/ 0 赞/ 135 阅读

相关字符串中的快速模式匹配0

字符串中的快速模式匹配1977 作者：DONALD E.KNUTH,JAMES H,MORRIS,JR.VAUGHAN R.PRATTY 发表时间：1977 摘要：这

梦里梦外;/ 2022年06月16日 06:21/ 0 赞/ 133 阅读

相关 poj--1961--Period

Period <table> <tbody> <tr> <td><strong>Time Limit:</strong> 3000MS</td>

亦凉/ 2022年06月09日 01:11/ 0 赞/ 107 阅读

相关 POJ - 1961 Period(KMP)

[点我看题][Link 1] 题意：找一个字符串S的前缀(包括本身)的循环节。分析：KMP模板题，先求出前缀表，然后对于每一个前缀，假设目前是前i个字符，他们的前后缀相等

分手后的思念是犯贱/ 2022年06月05日 08:48/ 0 赞/ 132 阅读

相关 (字符串的模式匹配4.7.18)POJ 1961 Period(求一个串到第i个字符循环节出现的次数)...

/ POJ_1961.cpp Created on: 2013年10月29日 Author: Adminis

小灰灰/ 2022年05月12日 22:36/ 0 赞/ 126 阅读

相关 POJ-1961 Period

Period <table> <tbody> <tr> <td><strong>Time Limit:</strong> 3000MS</td>

迷南。/ 2021年11月01日 04:26/ 0 赞/ 144 阅读