Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.io.*;
- import java.util.*;
- public class Main {
- public static int[] fail(String pat)
- {
- int n = pat.length();
- int[] failure = new int[n + 1];
- int cur_pos = 0;
- failure[0] = -1;
- for (int j = 1; j < n; j++)
- {
- int i = failure[j - 1];
- while ((pat.charAt(j) != pat.charAt(i + 1)) && i >= 0) {
- i = failure[i];
- }
- if (pat.charAt(j) == pat.charAt(i + 1)) {
- failure[j] = i + 1;
- }
- else {
- failure[j] = -1;
- cur_pos = j + 1;
- }
- }
- failure[n] = cur_pos;
- return failure;
- }
- public static void main(String args[]) {
- Scanner cin = new Scanner(System.in);
- String s = cin.nextLine();
- int[] F = new int[s.length() + 1];
- int result;
- while (!(s.charAt(0) == '.')) {
- F = fail(s);
- if (F[F.length - 2] < 0) {
- result = 1;
- }
- else if (F[F.length - 1] == 0 ) {
- result = F.length - 1;
- }
- else {
- result = (F[F.length-2] + 1) / (F[F.length - 1] + 1);
- }
- System.out.println(result);
- s = cin.nextLine();
- F = new int[s.length()+1];
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement