精华内容
下载资源
问答
  • 最小覆盖子串长度为n-next[n] ,n...所有前缀的最小重复子串,加一个循环即可。 附上代码喵: #include #include #include using namespace std; char name[1000010]; int nex[1000010]; void getnext() { memse

    最小覆盖子串长度为n-next[n] ,n为字符串长度。如果恰好覆盖就为n/(n-next[n]),否则为1.

    所有前缀的最小重复子串,加一个循环即可。


    附上代码喵:

    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    char name[1000010];
    int nex[1000010];
    void getnext()
    {
    	memset(nex,0,sizeof(nex));
    	nex[0]=-1;
    	int j=-1,k=0;
    	int len=strlen(name);
    	while(k<len)
    	{
    		if(j==-1||name[j]==name[k])
    		{
    			j++;k++;
    			nex[k]=j;
    		}
    		else
    			j=nex[j];
    	}
    }
    int main()
    {
    	int n,ica=1;
    
    	while(scanf("%d",&n),n)
    	{
    		scanf("%s",name);
    		printf("Test case #%d\n",ica++);
    		getnext();
    		for(int i=1;i<=n;i++)
    		{
    			int len=i-nex[i];
    			if(i%len==0&&i/len>1)
    			{
    				printf("%d %d\n",i,i/len);
    			}
    		}
    		printf("\n");
    	}
    	return 0;
    }


    展开全文
  • poj2406 kmp 最小重复子串

    千次阅读 2012-12-02 00:51:41
    这个题就是利用kmp的next函数,求组成主最小重复子串的长度。 如果字符下标从1开始的话,字符长度len (1)若len mod ( len - next[len] ) = 0 那么a[next[len]+1...len] 就是最小重复的子串 (2)若len ...

    这个题就是利用kmp的next函数,求组成主串的最小重复子串的长度。

    如果字符串下标从1开始的话,字符串长度len

    (1)若len mod ( len - next[len] ) = 0 那么a[next[len]+1...len] 就是最小重复的子串

    (2)若len mod ( len - next[len] ) !=0 那么最小重复子串为字符串本身

     

    #include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<string>
    using namespace std;
    
    const int maxn=1000001;
    int n;
    int fail[maxn];
    char a[maxn];
    
    void kmp()
    {
    	int i,j;
    	j=-1;
    	memset(fail,-1,sizeof(fail));
    	for(i=1;i<n;i++)
    	{
    		while(j>-1 && a[j+1]!=a[i]) j=fail[j];
    		if(a[j+1]==a[i]) j++;
    		fail[i]=j;
    	}
    }
    
    int main()
    {
    	while(scanf("%s",&a))
    	{	
    		if(a[0]=='.') break;
    		n=strlen(a);
    		kmp();
    		if(n%(n-1-fail[n-1])==0) cout<<n/(n-1-fail[n-1])<<endl;
    		else cout<<1<<endl;
    	}
    	return 0;
    }
    


     

    展开全文
  • public class LRS { public static void main(String[] args) { String X = "ABABABA"; System.out.println(nativeLRS(X)); } public static String nativeLRS(String x) { in
    public class LRS {
        public static void main(String[] args) {
            String X = "ABABABA";
            System.out.println(nativeLRS(X));
        }
    
        public static String nativeLRS(String x) {
            int length = x.length();
            int maxLength = 0;
            String max = null;
            for (int i =0; i < length; i++) {
                int len = 0;
                int k = i;
                for (int j = i+1; j < length; j++) {
                    len = statLen(x, k, j);
                    if (len > maxLength) {
                        maxLength = len;
                        max = x.substring(k, len);
                    }
                }
            }
            return max;
        }
    
        public static int statLen(String x, int k, int j) {
            int cur_len = 0;
            while(k < x.length() && j < x.length() && x.charAt(k) == x.charAt(j)) {
                k++;
                j++;
                cur_len++;
            }
            return cur_len;
        }
    }
    

    展开全文
  • 最小覆盖子串长度为n-next[n] ,n为字符长度。如果恰好覆盖就为n-next[n],否则为1. #include #include #include using namespace std; char name[1000010]; int nex[1000010]; void getnext() { memset(nex,0,...

    最小覆盖子串长度为n-next[n] ,n为字符串长度。如果恰好覆盖就为n/(n-next[n]),否则为1.


    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    char name[1000010];
    int nex[1000010];
    void getnext()
    {
    	memset(nex,0,sizeof(nex));
    	nex[0]=-1;
    	int j=-1,k=0;
    	int len=strlen(name);
    	while(k<len)
    	{
    		if(j==-1||name[j]==name[k])
    		{
    			j++;k++;
    			nex[k]=j;
    		}
    		else
    			j=nex[j];
    	}
    }
    int main()
    {
    	while(scanf("%s",name),strcmp(".",name)!=0)
    	{
    		getnext();
    		int l=strlen(name);
    		if(l%(l-nex[l])==0)
    			printf("%d\n",l/(l-nex[l]));
    		else
    			printf("1\n");
    	}
    	return 0;
    }


    展开全文
  • 求出最小覆盖子串,取模补齐。 #include #include const int maxn=101000; #define MIN(a,b) a typedef long long ll; char s[maxn]; int next[maxn]; void getnext() { memset(next,0,sizeof(next)); int j=...
  • KMP(最长重复子串 & 最小覆盖)

    千次阅读 2014-08-13 15:32:18
    KMP(最长重复子串 & 最小覆盖)
  • 题目:求这串字符中的重复次数最多的连续重复子串,多组答案输出字典序最小的那个串。 思路:与前一个题目几乎一样的,加上了字典序。多判断就好 //#include&lt;bits/stdc++.h&gt; #include&lt;...
  • 输出 一行 如果存在多种,输出最小的满足题意的数; 如果不存在,则输出-1. 样例输入 Copy 121212 样例输出 Copy 12 #include "bits/stdc++.h" typedef long long ll; using namespace std; string temp; bool ...
  • 求多组字符最小周期 如qwqwqwqw 最小周期为2 by小战*/ #include #include using namespace std; int main() { char s[100]; while(cin >> s) { int len = strlen(s); for(int i=1;i;i++) { if...
  • 76. 最小覆盖子串 给你一个字符 S、一个字符 T 。请你设计一种算法,可以在 O(n) 的时间复杂度内,从字符 S 里面找出:包含 T 所有字符的最小子。 示例: 输入:S = “ADOBECODEBANC”, T = “ABC” 输出:...
  • 在字符串中查找最长重复子串

    千次阅读 2013-09-08 17:43:06
    如何在字符串中查找最长重复子串?比如字符串"abcdtttabcd"的最长重复子串为“abcd”,...如果子串1的开始位置为i,那么子串1的重复子串(设为子串2)的开始位置最小为i+1。变量i从0开始遍历字符串,对于每个变
  • 1387 最长重复子串

    2012-03-26 09:28:11
    对于一个字符串S1,其中S2是他的一个子串(长度严格小于S1长度),如果S2在S1中出现次数超过1次,那么S2就是一个重复子串,现在的要求是给定S1,请求出他的最长重复子串; 如果有多个长度一样的最长子串,请输入...
  • 最长重复子串(可重复) 后缀数组

    千次阅读 2011-03-08 20:03:00
    最长重复子串时间限制:1000 ms | 内存限制:3000 KB 描述 对于一个字符串S1,其中S2是他的一个子串(长度严格小于S1长度),如果S2在S1中出现次数超过1次,那么S2就是一个重复子串,现在的要求是给定S1,请求出他...
  • 最大连续重复子串

    千次阅读 2009-10-18 16:49:00
    比如对于字符串abababcc,“ababab”是最大连续重复子串,其中“ab”重复次数是3。再比如:bbbaaa,问题的答案是“aaa”,”a“重复3次构成。虽然"bbb"也是由"b"连续三次构成,但是字典排序"aaa" 
  • 重复子串-LintCode

    2017-12-06 14:26:45
    给出一个整数数组,写一个程序把这个整数数组分成S1跟S2两部分,使S1中的和跟S2中的和的绝对值最小。如果有一个一个整数数组 S 有 n 个数,如果Subset1有 m 个数,Subset2必须有 n-m 个数并且 abs(sum(Subset1) – ...
  • =10^5,求它重复次数最多的连续重复子串(输出字典序最小的那个)。 例如ccabcabc,答案就是abcabc 一开始没想清楚,结果调了好久。 原理: 按照L划分,因为相邻两个i之间隔着一个L,s[i*L]和s[(i+1)*L]...
  • 给定一个含有n个正整数的数组和一个正整数s ,找出该数组中满足其和≥ s的长度最小的连续数组。如果不存在符合条件的连续数组,返回 0。 示例: 输入: s = 7, nums = [2,3,1,2,4,3] 输出: 2 解释: 数组[4,3]...
  • 最长重复子串(后缀数组)

    千次阅读 2010-08-13 19:40:00
    http://ds.bianchengla.com/course/3/practise/problem?id=1387最长重复子串时间限制:1000 ms | 内存限制:3000 KB 描述 对于一个字符串S1,其中S2是他的一个子串(长度严格小于S1长度),如果S2在S1中出现...
  • 题目描述: 如果一个串能被最多分成R个相同的连续串...比较两个答案的字典序的时候本来是要求最长公共前缀的,但是这个题可以直接用rank比较,因为两个都是重复次数相同的重复子串,如果长度一样,那么显然可以用ran...
  • 这个题是求这个重复子串,还得保证字典序最小 巧妙运用sa 看这个https://blog.csdn.net/queuelovestack/article/details/53035903 很清晰 #pragma comment(linker, "/STACK:1024000000,1024000000") #includ.....
  • 题目大意就是求重复次数最多的连续重复子串。例如abababc 答案就是ababab 因为ab连续出现的次数最多 并且题目还要求输出字典序最小的 比如abababcdcdcd  ababab和cdcdcd都符合要求 但是ababab字典序小 ...
  • 本题就是求重复数最多的字典序最小的$runs$,如果重复数为1,那么做法显然,然后只考虑重复数大于1的情况。 从小到大枚举长度$len$,对于每个关键点$x=i\times len$,有且仅有一个长度为$len$的经过它。 算出$x$...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 427
精华内容 170
关键字:

最小重复子串