Advertisement
Guest User

Untitled

a guest
Oct 6th, 2015
72
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.38 KB | None | 0 0
  1. import java.io.*;
  2. import java.util.*;
  3.  
  4. public class Main {
  5.  
  6. public static int[] fail(String pat)
  7. {
  8. int n = pat.length();
  9. int[] failure = new int[n + 1];
  10. int cur_pos = 0;
  11. failure[0] = -1;
  12. for (int j = 1; j < n; j++)
  13. {
  14. int i = failure[j - 1];
  15. while ((pat.charAt(j) != pat.charAt(i + 1)) && i >= 0) {
  16. i = failure[i];
  17. }
  18. if (pat.charAt(j) == pat.charAt(i + 1)) {
  19. failure[j] = i + 1;
  20. }
  21. else {
  22. failure[j] = -1;
  23. cur_pos = j + 1;
  24. }
  25. }
  26. failure[n] = cur_pos;
  27. return failure;
  28. }
  29.  
  30. public static void main(String args[]) {
  31. Scanner cin = new Scanner(System.in);
  32. String s = cin.nextLine();
  33. int[] F = new int[s.length() + 1];
  34. int result;
  35. while (!(s.charAt(0) == '.')) {
  36. F = fail(s);
  37. if (F[F.length - 2] < 0) {
  38. result = 1;
  39. }
  40. else if (F[F.length - 1] == 0 ) {
  41. result = F.length - 1;
  42. }
  43. else {
  44. result = (F[F.length-2] + 1) / (F[F.length - 1] + 1);
  45. }
  46. System.out.println(result);
  47. s = cin.nextLine();
  48. F = new int[s.length()+1];
  49. }
  50. }
  51. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement