fork download
copy 
  1. /* package whatever; // don't place package name! */
  2.  
  3. import java.util.*;
  4. import java.lang.*;
  5. import java.io.*;
  6.  
  7. /* Name of the class has to be "Main" only if the class is public. */
  8. class Ideone
  9. {
  10. 	public static void main (String[] args) throws java.lang.Exception
  11. 	{
  12. 		Scanner in = new Scanner(System.in);
  13. 		int t = Integer.parseInt(in.nextLine());
  14. 		int i=1;
  15. 		while(i <= t){
  16. 			int n = Integer.parseInt(in.nextLine());
  17. 			String input = in.nextLine();
  18. 			System.out.println("Test Case #"+i);
  19. 			periodString(input,n);
  20. 			i++;
  21. 			System.out.println();
  22. 		}
  23. 	}
  24.  
  25. 	private static void periodString(String in,int len){
  26. 		int[] lps = prefixTable(in);
  27. 		int i=0;
  28. 		int n;
  29. 		int k;
  30. 		for(i=0;i<len;i++){
  31. 			if(lps[i] != 0) {
  32. 				n = i+1; //length of string ..upto i.
  33. 				int t = n-lps[i];
  34. 				if(t > 0 && n % t == 0){
  35. 					k = n/t;
  36. 					System.out.println(n+" " +k);
  37. 				}
  38. 			}
  39. 		}
  40. 	}
  41.  
  42. 		private static int[] prefixTable(String pattern) {
  43. 		int n = pattern.length();
  44. 		int[] lps = new int[n];
  45. 		int len = 0; // length of common prefix n suffix
  46. 		lps[0] = 0;
  47. 		int i = 1;
  48. 		while (i < n) {
  49. 			if (pattern.charAt(i) == pattern.charAt(len)) {
  50. 				len++;
  51. 				lps[i] = len;
  52. 				i++;
  53. 			} else {
  54. 				if (len > 0) {
  55. 					len = lps[len - 1];
  56. 				} else {
  57. 					lps[i] = 0; // len = 0
  58. 					i++;
  59. 				}
  60. 			}
  61. 		}
  62. 		return lps;
  63. 	}
  64. }
Success #stdin #stdout 0.14s 321088KB
comments (?)
stdin
copy 
2
3
aaa
12
aabaabaabaab
stdout
copy 
Test Case #1
2 2
3 3

Test Case #2
2 2
6 2
9 3
12 4
https://ideone.com/KDry2b
language:
Java (HotSpot 12)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!