API tools faq
paste
Advertisement
osipyonok

!debug! пересечение, конкатенация, объединение, итерация авт

osipyonok
Jan 4th, 2017
171
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 14.83 KB | None | 0 0
raw download clone embed print report
  1. /* package whatever; // don't place package name! */
  2.  
  3. import java.util.*;
  4. import java.lang.*;
  5. import java.io.*;
  6.  
  7. /* Name of the class has to be "Main" only if the class is public. */
  8. class Main
  9. {
  10.     public static void main (String[] args) throws java.lang.Exception
  11.     {
  12.         Scanner sc = new Scanner(System.in);
  13.         int a = sc.nextInt();
  14.         int s = sc.nextInt();
  15.         Set<Integer> S = new HashSet();
  16.         for(int i = 0 ; i < s ; ++i)S.add(i);
  17.         int s0 = sc.nextInt();
  18.         --s0;
  19.         int sz_f = sc.nextInt();
  20.         Set<Integer> F = new HashSet();
  21.         for(int i = 0 ; i < sz_f ; ++i){
  22.             int t = sc.nextInt();
  23.             --t;
  24.             F.add(t);
  25.         }
  26.         Map<Pair<Integer , Character> , ArrayList<Integer>> f = new HashMap();
  27.         int k = sc.nextInt();
  28.         while(k-->0){
  29.             int u = sc.nextInt();
  30.             char ch = sc.next().charAt(0);
  31.             int v = sc.nextInt();
  32.             --u;
  33.             --v;
  34.             Pair<Integer , Character> fnd = new Pair<Integer , Character>(u , ch);
  35.             if(!f.containsKey(fnd)){
  36.                 //    System.out.println("fdsfsd");
  37.                 f.put(fnd, new ArrayList<Integer>());
  38.             }
  39.             ArrayList<Integer> tmp = f.get(fnd);
  40.             //tmp.add(v);
  41.             tmp.add(v);
  42.             f.put(fnd, tmp);
  43.         }
  44.         Automata<Integer> aut = new Automata<Integer>(a , S , s0 , F , f);
  45.         //System.out.println(aut);
  46.         System.out.println(aut.Iterate());
  47.     }
  48. }
  49.  
  50. class Automata<T > {
  51.     int A;
  52.     T s;
  53.     Set<T> S = new HashSet<T>();
  54.     Set<T> F = new HashSet<T>();
  55.     Map<Pair<T , Character> , ArrayList<T>> f = new HashMap();
  56.     Map<Pair<T , T> , ArrayList<Character>> inverse_f = new HashMap();
  57.  
  58.     Automata(int _A , Set<T> _S , T _s , Set<T> _F , Map<Pair<T , Character> , ArrayList<T>> _f){
  59.         A = _A;
  60.         s = _s;
  61.         S = _S;
  62.         F = _F;
  63.         f = _f;
  64.         for(Map.Entry<Pair<T , Character> , ArrayList<T>> i : f.entrySet()){
  65.             Pair<T , ArrayList<T>> pr = new Pair<T , ArrayList<T>>(i.getKey().first() , i.getValue());
  66.             for(T cur : pr.second()){
  67.                 Pair<T,T> cp = new Pair<T,T>(pr.first() , cur);
  68.                 if(!inverse_f.containsKey(cp)){
  69.                     inverse_f.put(cp , new ArrayList<Character>());
  70.                 }
  71.                 if(!inverse_f.get(cp).contains(i.getKey().second())){
  72.                     inverse_f.get(cp).add(i.getKey().second());
  73.                 }
  74.             }
  75.         }
  76.     }
  77.  
  78.     public String toString(){
  79.         String res = "";
  80.         res += A;
  81.         res += '\n';
  82.         res += S.size() + "\n";
  83.         res += S.toString() + "\n";
  84.         res += s.toString() + "\n";
  85.         res += F.size() + "\n";
  86.         res += F.toString() + "\n";
  87.         res += f.toString();
  88.         return res;
  89.     }
  90.  
  91.     public Automata<Pair<Integer , T>> Iterate(){
  92.         int new_A = this.A;
  93.         Set<Pair<Integer , T> > new_S = new HashSet();
  94.         for(T i : this.S){
  95.             new_S.add(new Pair<Integer , T>(1 , i));
  96.         }
  97.         Pair<Integer , T> new_s = new Pair(2 , this.s);
  98.         new_S.add(new_s);
  99.         Set<Pair<Integer , T> > new_F = new HashSet();
  100.         for(T i : this.F){
  101.             new_F.add(new Pair<Integer , T>(1 , i));
  102.         }
  103.         new_F.add(new_s);
  104.         Map<Pair<Pair<Integer , T> , Character> , ArrayList<Pair<Integer , T>> > new_f = new HashMap();
  105.  
  106.         for(Pair<T , Character> key : this.f.keySet()){
  107.             boolean ck = this.F.contains(key.first());
  108.             if(this.F.contains(key.first())){
  109.                 if(this.f.containsKey(new Pair(this.s , key.second()))){
  110.                     ArrayList<T> to = this.f.get(new Pair(this.s , key.second()));
  111.                     Pair<Integer , T> new_key1 = new Pair<Integer , T>(1 , key.first());
  112.                     Pair<Pair<Integer , T> , Character> new_key = new Pair(new_key1 , key.second());
  113.                     if(!new_f.containsKey(new_key)){
  114.                         new_f.put(new_key , new ArrayList<Pair<Integer,T>>());
  115.                     }
  116.                     for(T v : to){
  117.                         new_f.get(new_key).add(new Pair<Integer , T>(1 , v));
  118.                     }
  119.                 }
  120.             }
  121.             ArrayList<T> to = this.f.get(key);
  122.             Pair<Integer , T> new_key1 = new Pair<Integer , T>(1 , key.first());
  123.             Pair<Pair<Integer , T> , Character> new_key = new Pair(new_key1 , key.second());
  124.             for(T v : to){
  125.                 if(!new_f.containsKey(new_key)){
  126.                     new_f.put(new_key , new ArrayList<Pair<Integer,T>>());
  127.                 }
  128.                 new_f.get(new_key).add(new Pair<Integer , T>(1 , v));
  129.                 if(ck){
  130.  
  131.                 }
  132.             }
  133.         }
  134.         for(char c = 'a' ; c < 'a' + A ; ++c){
  135.             Pair<T , Character> cur = new Pair(this.s , c);
  136.        //     System.out.println("cur: " + cur + " f: " + f);
  137.             for(Pair<T , Character> key : f.keySet()) {
  138.                 if (key.first().equals(cur.first()) && key.second().equals(cur.second())) {
  139.                     Pair<Pair<Integer, T>, Character> pt = new Pair<Pair<Integer, T>, Character>(new_s, c);
  140.                     if (!f.containsKey(pt)) {
  141.                         new_f.put(pt, new ArrayList<Pair<Integer, T>>());
  142.                     }
  143.                     ArrayList<T> to = f.get(key);
  144.                     if(to == null)continue;
  145.                     for (T v : to) {
  146.                         Pair<Integer, T> p = new Pair(1, v);
  147.  
  148.                         new_f.get(pt).add(p);
  149.                     }
  150.                 }
  151.             }
  152.         }
  153.  
  154.  
  155.         Automata<Pair<Integer , T> > res = new Automata<Pair<Integer , T> >(new_A , new_S , new_s , new_F , new_f);
  156.         return res;
  157.     }
  158.  
  159.     public Automata<Pair<Integer , T>> Concat(Automata<T> b){
  160.         int new_A = Math.max(this.A , b.A);
  161.         Set<Pair<Integer , T> > new_S = new HashSet();
  162.         for(T i : this.S){
  163.             new_S.add(new Pair<Integer , T>(1 , i));
  164.         }
  165.         for(T i : b.S){
  166.             new_S.add(new Pair<Integer , T>(2 , i));
  167.         }
  168.         Pair<Integer , T> new_s = new Pair(1 , this.s);
  169.         Set<Pair<Integer , T> > new_F = new HashSet();
  170.         for(T i : b.F){
  171.             new_F.add(new Pair<Integer , T>(2 , i));
  172.         }
  173.         if(/*тут должна быть проверка на допустимость пустого слова*/b.F.contains(b.s)){
  174.             for(T i : this.F){
  175.                 new_F.add(new Pair<Integer , T>(1 , i));
  176.             }
  177.         }
  178.         Map<Pair<Pair<Integer , T> , Character> , ArrayList<Pair<Integer , T>> > new_f = new HashMap();
  179.         for(Pair<T , Character> key : b.f.keySet()){
  180.             ArrayList<T> to = b.f.get(key);
  181.             Pair<Integer , T> new_key1 = new Pair<Integer , T>(2 , key.first());
  182.             Pair<Pair<Integer , T> , Character> new_key = new Pair(new_key1 , key.second());
  183.             for(T v : to){
  184.                 if(!new_f.containsKey(new_key)){
  185.                     new_f.put(new_key , new ArrayList<Pair<Integer,T>>());
  186.                 }
  187.                 new_f.get(new_key).add(new Pair<Integer , T>(2 , v));
  188.             }
  189.         }
  190.         for(Pair<T , Character> key : this.f.keySet()){
  191.             ArrayList<T> to = this.f.get(key);
  192.             Pair<Integer , T> new_key1 = new Pair<Integer , T>(1 , key.first());
  193.             Pair<Pair<Integer , T> , Character> new_key = new Pair(new_key1 , key.second());
  194.             for(T v : to){
  195.                 if(!new_f.containsKey(new_key)){
  196.                     new_f.put(new_key , new ArrayList<Pair<Integer,T>>());
  197.                 }
  198.                 new_f.get(new_key).add(new Pair<Integer , T>(1 , v));
  199.             }
  200.         }
  201.         for(char c = 'a' ; c < 'a' + A ; ++c){
  202.             Pair<T , Character> cur = new Pair(b.s , c);
  203.             //     System.out.println("cur: " + cur + " f: " + f);
  204.             for(Pair<T , Character> key : b.f.keySet()) {
  205.                 if (key.first().equals(cur.first()) && key.second().equals(cur.second())) {
  206.                     Pair<Pair<Integer, T>, Character> pt = new Pair<Pair<Integer, T>, Character>(new_s, c);
  207.                     if (!b.f.containsKey(pt)) {
  208.                         new_f.put(pt, new ArrayList<Pair<Integer, T>>());
  209.                     }
  210.                     ArrayList<T> to = b.f.get(key);
  211.                     if(to == null)continue;
  212.                     for (T v : to) {
  213.                         Pair<Integer, T> p = new Pair(1, v);
  214.  
  215.                         new_f.get(pt).add(p);
  216.                     }
  217.                 }
  218.             }
  219.         }
  220.         Automata<Pair<Integer , T> > res = new Automata<Pair<Integer , T> >(new_A , new_S , new_s , new_F , new_f);
  221.         return res;
  222.     }
  223.  
  224.     public Automata<Pair<Integer , T>> Add(Automata<T> b){
  225.         int new_A = Math.max(this.A , b.A);
  226.         Set<Pair<Integer , T> > new_S = new HashSet();
  227.         for(T i : this.S){
  228.             new_S.add(new Pair<Integer , T>(1 , i));
  229.         }
  230.         for(T i : b.S){
  231.             new_S.add(new Pair<Integer , T>(2 , i));
  232.         }
  233.         Pair<Integer , T> new_s = new Pair<Integer , T>(3 , this.s);
  234.         new_S.add(new_s);
  235.         Set<Pair<Integer , T> > new_F = new HashSet();
  236.         for(T i : this.F){
  237.             new_F.add(new Pair<Integer , T>(1 , i));
  238.         }
  239.         for(T i : b.F){
  240.             new_F.add(new Pair<Integer , T>(2 , i));
  241.         }
  242.         if(/*тут должна быть проверка на допустимость пустого слова*/ this.F.contains(this.s) || b.F.contains(b.s)){
  243.             new_F.add(new_s);
  244.         }
  245.         Map<Pair<Pair<Integer , T> , Character> , ArrayList<Pair<Integer , T>> > new_f = new HashMap();
  246.         for(Pair<T , Character> key : this.f.keySet()){
  247.             ArrayList<T> to = this.f.get(key);
  248.             Pair<Integer , T> new_key1 = new Pair<Integer , T>(1 , key.first());
  249.             Pair<Pair<Integer , T> , Character> new_key = new Pair(new_key1 , key.second());
  250.             for(T v : to){
  251.                 if(!new_f.containsKey(new_key)){
  252.                     new_f.put(new_key , new ArrayList<Pair<Integer,T>>());
  253.                 }
  254.                 new_f.get(new_key).add(new Pair<Integer , T>(1 , v));
  255.             }
  256.         }
  257.         for(Pair<T , Character> key : b.f.keySet()){
  258.             ArrayList<T> to = b.f.get(key);
  259.             Pair<Integer , T> new_key1 = new Pair<Integer , T>(2 , key.first());
  260.             Pair<Pair<Integer , T> , Character> new_key = new Pair(new_key1 , key.second());
  261.             for(T v : to){
  262.                 if(!new_f.containsKey(new_key)){
  263.                     new_f.put(new_key , new ArrayList<Pair<Integer,T>>());
  264.                 }
  265.                 new_f.get(new_key).add(new Pair<Integer , T>(2 , v));
  266.             }
  267.         }
  268.         for(char c = 'a' ; c < 'a' + new_A ; ++c){
  269.             if(this.f.containsKey(new Pair<T , Character>(this.s , c))){
  270.                 if(!new_f.containsKey(new Pair(new_s , c))){
  271.                     new_f.put(new Pair(new_s , c) , new ArrayList<Pair<Integer , T>>());
  272.                 }
  273.                 ArrayList<T> to = this.f.get(new Pair<T , Character>(this.s , c));
  274.                 for(T v : to){
  275.                     new_f.get(new Pair(new_s , c)).add(new Pair<Integer , T>(1 , v));
  276.                 }
  277.             }
  278.             if(b.f.containsKey(new Pair<T , Character>(b.s , c))){
  279.                 if(!new_f.containsKey(new Pair(new_s , c))){
  280.                     new_f.put(new Pair(new_s , c) , new ArrayList<Pair<Integer , T>>());
  281.                 }
  282.                 ArrayList<T> to = b.f.get(new Pair<T , Character>(b.s , c));
  283.                 for(T v : to){
  284.                     new_f.get(new Pair(new_s , c)).add(new Pair<Integer , T>(2 , v));
  285.                 }
  286.             }
  287.         }
  288.         Automata<Pair<Integer , T> > res = new Automata<Pair<Integer , T> >(new_A , new_S , new_s , new_F , new_f);
  289.         return res;
  290.     }
  291.  
  292.     public Automata<Pair<T , T> > Multiply (Automata<T> b){
  293.         int new_A = Math.max(this.A, b.A);
  294.         Set<Pair<T , T> > new_S = new HashSet<Pair<T , T> >();
  295.         for(T i: this.S){
  296.             for(T j: b.S){
  297.                 Pair<T , T> pr = new Pair<T, T>(i , j);
  298.                 new_S.add(pr);
  299.             }
  300.         }
  301.         Set<Pair<T , T> > new_F = new HashSet<Pair<T , T> >();
  302.         for(T i: this.F){
  303.             for(T j: b.F){
  304.                 Pair<T , T> pr = new Pair<T , T>(i , j);
  305.                 new_F.add(pr);
  306.             }
  307.         }
  308.         Pair<T , T> new_s = new Pair<T , T>(this.s , b.s);
  309.         Map<Pair<Pair<T , T> , Character> , ArrayList<Pair<T , T>> > new_f = new HashMap();
  310.  
  311.         for(Pair<T , Character> i : this.f.keySet()){
  312.             for(Pair<T , Character> j : b.f.keySet()){
  313.                 if(i.second() != j.second())continue;
  314.                 for(Pair<T , T> k : new_S){
  315.                     if(i.first() == k.first() && j.first() == k.second()){
  316.                         Pair<Pair<T , T> , Character> pr = new Pair<Pair<T , T> , Character>(k , (char)i.second());
  317.                         // Pair<T , T> put_pair = new Pair<T, T>(this.f.get(i) , b.f.get(j));
  318.                         ArrayList<T> tf = this.f.get(i);
  319.                         ArrayList<T> bf = b.f.get(i);
  320.                         for(T curt : tf){
  321.                             for(T curb : bf){
  322.                                 Pair<T , T> put_pair = new Pair<T , T>(curt , curb);
  323.                                 if(!new_f.containsKey(pr)){
  324.                                     new_f.put(pr , new ArrayList<Pair<T , T>>());
  325.                                 }
  326.                                 new_f.get(pr).add(put_pair);
  327.                             }
  328.                         }
  329.                     }
  330.                 }
  331.             }
  332.         }
  333.         Automata<Pair<T , T> > res = new Automata<Pair<T , T> >(new_A , new_S , new_s , new_F , new_f);
  334.         return res;
  335.     }
  336.  
  337. }
  338.  
  339. class Pair<T1 , T2 >{
  340.     T1 x;
  341.     T2 y;
  342.     Pair(T1 _x , T2 _y){
  343.         x = _x;
  344.         y = _y;
  345.     }
  346.     T1 first(){
  347.         return x;
  348.     }
  349.     T2 second(){
  350.         return y;
  351.     }
  352.     public String toString(){
  353.         return "{" + x.toString() + " ; " + y.toString() + "}";
  354.     }
  355.  
  356.     public boolean equals(Object other){
  357.         if (other instanceof Pair) {
  358.             Pair otherPair = (Pair) other;
  359.             return
  360.                     ((  this.x == otherPair.x ||
  361.                             ( this.x != null && otherPair.x != null &&
  362.                                     this.x.equals(otherPair.x))) &&
  363.                             (   this.y == otherPair.y ||
  364.                                     ( this.y != null && otherPair.y != null &&
  365.                                             this.y.equals(otherPair.y))) );
  366.         }
  367.         return false;
  368.     }
  369.  
  370. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!