Advertisement
anasretdinov

PrefixFun. CnuttMorisPratt

Apr 2nd, 2020
277
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 1.15 KB | None | 0 0
  1. import java.io.*;
  2. import java.util.*;
  3.  
  4. public class Uyi{
  5.     public static Scanner s = new Scanner(System.in);
  6.     public static PrintWriter out = new PrintWriter(System.out, true);
  7.  
  8.  
  9.     public static void main(String[] args) {
  10.         String s1 = s.next();
  11.         String s2 = s.next();
  12.         String s3 = s2 + '#' + s1;
  13.         int [] prefix = prefix(s3);
  14.         int counter = 0;
  15.         ArrayList<Integer> list = new ArrayList<>();
  16.         for (int i = s2.length(); i < s3.length(); i++) {
  17.             if (prefix[i] == s2.length()){
  18.                 counter++;
  19.                 list.add(i - 2 * s2.length());
  20.             }
  21.         }
  22.         System.out.println(counter);
  23.         for (int x: list) {
  24.             System.out.println((x+1) + " ");
  25.         }
  26.     }
  27.     static int [] prefix (String sk){
  28.         char [] s = sk.toCharArray();
  29.         int n = sk.length();
  30.         int [] pi = new int [n];
  31.         for (int i = 1; i < n; i++) {
  32.             int j = pi[i-1];
  33.             while (j > 0 && s[i] != s[j])
  34.                 j = pi[j-1];
  35.             if (s[i] == s[j])  ++j;
  36.             pi[i] = j;
  37.         }
  38.         return pi;
  39.     }
  40. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement