Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.util.Scanner;
- import java.util.TreeSet;
- public class Exam {
- public static class Pair implements Comparable<Pair> {
- long first;
- long second;
- public Pair(long first, long second) {
- this.first = first;
- this.second = second;
- }
- @Override
- public int compareTo(Pair o) {
- // TODO Auto-generated method stub
- if (this.first>o.first) {
- return 1;
- } else if (this.first==o.first && this.second==o.second) {
- return 0;
- }
- return 0;
- }
- }
- public static void main(String[] args) {
- TreeSet<Pair> set = new TreeSet<Pair>();
- int[] fre = new int[30];
- int[] frearr= new int[30];
- long[][] hsh= new long[2][200005];
- long[][] pows = new long[2][200005];
- long MOD = 1000000007;
- long MOD2 = 1000000009;
- Scanner sc = new Scanner(System.in);
- String s = sc.next();
- String t = sc.next();
- int N = s.length();
- int M = t.length();
- char[] S = s.toCharArray();
- char[] T = t.toCharArray();
- pows[0][0] = pows[1][0] = 1;
- for(int i = 1; i<=M; i++){
- pows[0][i] = pows[0][i-1]*37%MOD;
- pows[1][i] = pows[1][i-1]*131%MOD2;
- }
- for(int i= 1; i<=M; i++){
- hsh[0][i] = hsh[0][i-1]*37 + T[i-1]-'a' + 1;
- hsh[1][i] = hsh[1][i-1]*131 + T[i-1]-'a' + 1;
- hsh[0][i] %= MOD;
- hsh[1][i] %= MOD2;
- }
- for(int i = 1; i<=N; i++){
- fre[S[i-1]-'a']++;
- }
- int r = 1;
- while(r < N){
- frearr[T[r-1]-'a']++;
- r++;
- }
- for(int l = 1; r<=M; r++){
- frearr[T[r-1]-'a']++;
- boolean good = true;
- for(int c = 0; c<26; c++){
- if(frearr[c] != fre[c]){
- good = false;
- }
- }
- if(good){
- long h1 = ((hsh[0][r] - hsh[0][l-1]*pows[0][N])%MOD+MOD)%MOD;
- long h2 = ((hsh[1][r] - hsh[1][l-1]*pows[1][N])%MOD2+MOD2)%MOD2;
- set.add(new Pair(h1,h2));
- }
- frearr[T[l-1]-'a']--;
- l++;
- }
- System.out.println(set.size());
- //cout << kt.size() << "\n";
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement