Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.io.BufferedReader;
- import java.io.IOException;
- import java.io.InputStreamReader;
- import java.io.PrintWriter;
- import java.util.Arrays;
- import java.util.HashSet;
- import java.util.StringTokenizer;
- import static java.lang.Math.*;
- /**
- * Created by IntelliJ IDEA.
- * User: Taras_Brzezinsky
- * Date: 6/18/11
- * Time: 10:15 PM
- * To change this template use File | Settings | File Templates.
- */
- public class B_tb extends Thread {
- private static final int MODULO = 31;
- public B_tb(){
- this.setPriority(Thread.MAX_PRIORITY);
- this.input = new BufferedReader(new InputStreamReader(System.in));
- this.output = new PrintWriter(System.out);
- this.tokens = null;
- }
- public void run(){
- try{
- String all = nextToken();
- String begin = nextToken();
- String end = nextToken();
- long[] powers = new long[6000];
- powers[0] = 1;
- for (int i = 1; i < 6000; ++i) {
- powers[i] = powers[i - 1] * MODULO;
- }
- HashSet<Long> finalHashes = new HashSet<Long>();
- long[] hashed = new long[all.length()];
- long beginHash = 0, endHash = 0;
- for (int i = 0; i < begin.length(); ++i) {
- beginHash += (begin.charAt(i) - 'a' + 1) * powers[i];
- }
- for (int i = 0; i < end.length(); ++i) {
- endHash += (end.charAt(i) - 'a' + 1) * powers[i];
- }
- hashed[0] = all.charAt(0) - 'a' + 1;
- for (int i = 1; i < all.length(); ++i) {
- hashed[i] = hashed[i - 1] + (all.charAt(i) - 'a' + 1) * powers[i];
- }
- int ret = 0;
- int size = max(begin.length(), end.length());
- for (int len = size; len <= all.length(); ++len) {
- finalHashes.clear();
- for (int i = 0; i + len <= all.length(); ++i) {
- int j = i + len - 1;
- long currentBegin = hashed[i + begin.length() - 1] - (i == 0 ? 0 : hashed[i - 1]);
- long currentEnd = hashed[j] - (j - end.length() + 1 == 0 ? 0 : hashed[j - end.length()]);
- if (currentBegin == beginHash * powers[i] && currentEnd == endHash * powers[j - end.length() + 1]) {
- finalHashes.add((hashed[j] - (i == 0 ? 0 : hashed[i - 1])) * powers[5500 - j]);
- }
- }
- ret += finalHashes.size();
- }
- output.println(ret);
- output.flush();
- output.close();
- } catch (Throwable e) {
- System.err.println(e.getMessage());
- System.err.println(Arrays.deepToString(e.getStackTrace()));
- }
- }
- public static void main(String []args){
- new B_tb().start();
- }
- private int nextInt() throws IOException{
- return Integer.parseInt(nextToken());
- }
- private double nextDouble() throws IOException{
- return Double.parseDouble(nextToken());
- }
- private long nextLong() throws IOException{
- return Long.parseLong(nextToken());
- }
- private String nextToken() throws IOException {
- while (tokens == null || !tokens.hasMoreTokens()){
- tokens = new StringTokenizer(input.readLine());
- }
- return tokens.nextToken();
- }
- private BufferedReader input;
- private PrintWriter output;
- private StringTokenizer tokens;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement