Advertisement
Guest User

Untitled

a guest
Feb 21st, 2020
143
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.87 KB | None | 0 0
  1. import java.util.Scanner;
  2. import java.util.TreeSet;
  3. public class Exam {
  4. public static class Pair implements Comparable<Pair> {
  5. long first;
  6. long second;
  7. public Pair(long first, long second) {
  8. this.first = first;
  9. this.second = second;
  10. }
  11. @Override
  12. public int compareTo(Pair o) {
  13. // TODO Auto-generated method stub
  14. if (this.first>o.first) {
  15. return 1;
  16. } else if (this.first==o.first && this.second==o.second) {
  17. return 0;
  18. }
  19. return 0;
  20. }
  21. }
  22. public static void main(String[] args) {
  23. TreeSet<Pair> set = new TreeSet<Pair>();
  24. int[] fre = new int[30];
  25. int[] frearr= new int[30];
  26. long[][] hsh= new long[2][200005];
  27. long[][] pows = new long[2][200005];
  28. long MOD = 1000000007;
  29. long MOD2 = 1000000009;
  30. Scanner sc = new Scanner(System.in);
  31. String s = sc.next();
  32. String t = sc.next();
  33. int N = s.length();
  34. int M = t.length();
  35. char[] S = s.toCharArray();
  36. char[] T = t.toCharArray();
  37. pows[0][0] = pows[1][0] = 1;
  38. for(int i = 1; i<=M; i++){
  39. pows[0][i] = pows[0][i-1]*37%MOD;
  40. pows[1][i] = pows[1][i-1]*131%MOD2;
  41. }
  42. for(int i= 1; i<=M; i++){
  43. hsh[0][i] = hsh[0][i-1]*37 + T[i-1]-'a' + 1;
  44. hsh[1][i] = hsh[1][i-1]*131 + T[i-1]-'a' + 1;
  45. hsh[0][i] %= MOD;
  46. hsh[1][i] %= MOD2;
  47. }
  48. for(int i = 1; i<=N; i++){
  49. fre[S[i-1]-'a']++;
  50. }
  51. int r = 1;
  52. while(r < N){
  53. frearr[T[r-1]-'a']++;
  54. r++;
  55. }
  56. for(int l = 1; r<=M; r++){
  57. frearr[T[r-1]-'a']++;
  58. boolean good = true;
  59. for(int c = 0; c<26; c++){
  60. if(frearr[c] != fre[c]){
  61. good = false;
  62. }
  63. }
  64. if(good){
  65. long h1 = ((hsh[0][r] - hsh[0][l-1]*pows[0][N])%MOD+MOD)%MOD;
  66. long h2 = ((hsh[1][r] - hsh[1][l-1]*pows[1][N])%MOD2+MOD2)%MOD2;
  67. set.add(new Pair(h1,h2));
  68. }
  69. frearr[T[l-1]-'a']--;
  70. l++;
  71. }
  72. System.out.println(set.size());
  73. //cout << kt.size() << "\n";
  74. }
  75. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement