Cod sursa(job #2059909)

Utilizator alexnekiNechifor Alexandru alexneki Data 7 noiembrie 2017 18:58:11
Problema Potrivirea sirurilor Scor 80
Compilator java Status done
Runda Arhiva educationala Marime 2.11 kb

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.Scanner;

public class Main {

  public static void main(String[] args) throws FileNotFoundException, IOException {
    Scanner in = new Scanner(new BufferedReader(new FileReader("strmatch.in")));
    PrintWriter out = new PrintWriter(new BufferedWriter(new FileWriter("strmatch.out")));
    String a = in.next();
    String b = in.next();
    //we need to find a in b

    int[] pre = new int[a.length()]; //pre[i] = the longest prefix of substring [0..i] that is also a proper suffix of [0..i]

    pre[0] = 0;
    int i = 1; //we are evaluating pre[i] (i is index where suffix ends)
    int j = 0; //j is index where prefix ends
    while (i < a.length()) {
      if (a.charAt(i) == a.charAt(j)) {
        pre[i] = j + 1;
        i++;
        j++;
      } else {
        if (j == 0) {
          pre[i] = 0;
          i++;
        } else {
          j = pre[j - 1];
        }
      }
    }

//    for (int k = 0; k < pre.length; k++) {
//      System.out.print(pre[k] + " ");
//    }
//    System.out.println();

    i = 0; //now i is the index in the pattern
    j = 0; //now j is the index in the big string (can never decrease)
    int sol = 0; //no. of solutions
    int[] poz = new int[1000];
    while (j < b.length()) {
//      System.out.println(i + " and " + j);
      if (a.charAt(i) == b.charAt(j)) {
        i++;
        j++;
        if (i == a.length()) {
          i = pre[i - 1];
          sol++;
          if (sol <= 1000) {
            poz[sol - 1] = j - a.length();
//            System.out.println(" => sol " + sol + ": " + poz[sol - 1]);
          }
        }
      } else {
        if (i == 0) {
          j++;
        } else {
          i = pre[i - 1];
        }
      }
    }
    out.println(sol);
    i = 0;
    while (i < sol && i < 1000) {
      out.print(poz[i] + " ");
      i++;
    }
    in.close();
    out.close();
  }
}