Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.io.*;
- import java.util.*;
- public class Uyi{
- public static Scanner s = new Scanner(System.in);
- public static PrintWriter out = new PrintWriter(System.out, true);
- public static void main(String[] args) {
- String s1 = s.next();
- String s2 = s.next();
- String s3 = s2 + '#' + s1;
- int [] prefix = prefix(s3);
- int counter = 0;
- ArrayList<Integer> list = new ArrayList<>();
- for (int i = s2.length(); i < s3.length(); i++) {
- if (prefix[i] == s2.length()){
- counter++;
- list.add(i - 2 * s2.length());
- }
- }
- System.out.println(counter);
- for (int x: list) {
- System.out.println((x+1) + " ");
- }
- }
- static int [] prefix (String sk){
- char [] s = sk.toCharArray();
- int n = sk.length();
- int [] pi = new int [n];
- for (int i = 1; i < n; i++) {
- int j = pi[i-1];
- while (j > 0 && s[i] != s[j])
- j = pi[j-1];
- if (s[i] == s[j]) ++j;
- pi[i] = j;
- }
- return pi;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement