1  import java.io.LineNumberReader;
  2  import java.io.FileReader;
  3  import java.io.File;
  4  import java.util.ArrayList;
  5  import java.util.Iterator;
  6
  7  public class rx
  8  {
  9      private String patternFromFile;
 10      private String stringFromFile;
 11
 12      public static void main(String[] args) throws Exception
 13      {
 14          long l = System.currentTimeMillis();
 15          rx instance = new rx(args[0]);
 16          boolean b = false;
 17          try
 18          {
 19              b = instance.check();
 20          }
 21          catch (Exception e)
 22          {
 23          }
 24          System.out.println("Match = " + b);
 25          l = System.currentTimeMillis() - l;
 26          System.out.println("Spent time = " + l);
 27      }
 28
 29      private boolean check() throws Exception
 30      {
 31          System.out.println("stringFromFile = " + stringFromFile);
 32          System.out.println("patternFromFile = " + patternFromFile);
 33
 34          if(stringFromFile.indexOf("*") >-1 || stringFromFile.indexOf("?") >-1 )
 35          {
 36              while(stringFromFile.indexOf("**") > -1)
 37                  stringFromFile = stringFromFile.replaceAll("\\*\\*","\\*");
 38              return check(patternFromFile, stringFromFile);
 39          }
 40          while(patternFromFile.indexOf("**") > -1)
 41              patternFromFile = patternFromFile.replaceAll("\\*\\*","\\*");
 42          return check(stringFromFile, patternFromFile);
 43      }
 44
 45      private boolean check(String string, String pattern) throws Exception
 46      {
 47          if(string.equals("") || pattern.equals(""))
 48          {
 49              return string.equals(pattern) || pattern.equals("*");
 50          }
 51
 52          ArrayList patternElements = new ArrayList();
 53          ArrayList tokens = splitByChar(pattern,'*', true);
 54
 55          int countOfSymbolsPattern = 0;
 56          int countOfAsterisks = 0;
 57          int countOfSymbolsString = string.length();
 58
 59          for (Iterator iterator = tokens.iterator(); iterator.hasNext();)
 60          {
 61              String s = (String) iterator.next();
 62              if(s.equals("*"))
 63              {
 64                  countOfAsterisks++;
 65              }
 66              else
 67              {
 68                  countOfSymbolsPattern += s.length();
 69              }
 70              patternElements.add(s);
 71          }
 72
 73          //trivial
 74          if((countOfAsterisks == 0 && countOfSymbolsPattern != countOfSymbolsString) ||
 75                  (countOfSymbolsPattern > countOfSymbolsString))
 76          {
 77              return false;
 78          }
 79
 80          if(patternElements.size() == 1)
 81          {
 82              String s2 = (String) patternElements.get(0);
 83              if(!s2.equals("*"))
 84              {
 85                  return match(string, s2);
 86              }
 87              else
 88              {
 89                  return true;
 90              }
 91          }
 92          else
 93          if(patternElements.size() == 2)
 94          {
 95              String s1 = (String) patternElements.get(0);
 96              String s2 = (String) patternElements.get(1);
 97              if(s1.equals("*"))
 98              {
 99                  if(string.length() >= s2.length())
100                  {
101                      return match(string.substring(string.length() - s2.length()), s2);
102                  }
103                  else
104                  {
105                      return false;
106                  }
107              }
108              else
109              {
110                  if(s2.equals("*"))
111                  {
112                      if(string.length() >= s1.length())
113                      {
114                          return match(string.substring(string.length() - s1.length()), s1);
115                      }
116                      else
117                      {
118                          return false;
119                      }
120                  }
121              }
122          }
123
124          boolean previousWasAsterisk = false;
125          for (int curPatternIndex = 0; curPatternIndex < patternElements.size(); curPatternIndex++)
126          {
127              String curPattern = (String) patternElements.get(curPatternIndex);
128              if(!curPattern.equals("*"))
129              {
130                  //then founding all possible occurences
131                  ArrayList positions = findPositions(string, curPattern);
132                  if(positions.size() == 0)
133                  {
134                      throw new Exception("not found any matches");
135                  }
136                  if(previousWasAsterisk)
137                  {
138                      for (Iterator iterator1 = positions.iterator(); iterator1.hasNext();)
139                      {
140                          Integer integer = (Integer) iterator1.next();
141                          int index = integer.intValue();
142
143                          boolean b1 = curPatternIndex < patternElements.size() - 2;
144                          if(b1)
145                          {
146                              String s2 = string.substring(index + curPattern.length());
147                              String pattern2 = getPatternRange(curPatternIndex + 1, patternElements.size(), patternElements);
148                              boolean check = check(s2, pattern2);
149                              if(check)
150                                  return check;
151                          }
152                          else
153                          {
154                              return string.endsWith(curPattern);
155                          }
156                      }
157                      return false;
158                  }
159                  else
160                  {
161                      Integer integer = (Integer) positions.get(0);
162                      int index = integer.intValue();
163                      if(index != 0)
164                      {
165                          return false;
166                      }
167
168                      if(index + curPattern.length() <= string.length() && curPatternIndex < patternElements.size() - 1)
169                      {
170                          String s2 = string.substring(index + curPattern.length());
171                          String pattern2 = getPatternRange(curPatternIndex + 1, patternElements.size(), patternElements);
172                          return check(s2, pattern2);
173                      }
174                  }
175
176                  previousWasAsterisk = false;
177              }
178              else
179              {
180                  previousWasAsterisk = true;
181              }
182          }
183
184          return previousWasAsterisk;
185      }
186
187      private String getPatternRange(int start, int end, ArrayList patternElements)
188      {
189          StringBuffer stringBuffer = new StringBuffer();
190          for(int i = start; i < end; i++)
191          {
192              stringBuffer.append((String) patternElements.get(i));
193          }
194          return stringBuffer.toString();
195      }
196
197      private ArrayList findPositions(String string, String s)
198      {
199          ArrayList positions = new ArrayList();
200          if(string.length() < s.length())
201          {
202              return positions;
203          }
204          for(int i=0; i<= string.length() - s.length(); i++)
205          {
206              if(match(string.substring(i, i + s.length()), s))
207              {
208                  positions.add(new Integer(i));
209              }
210          }
211          return positions;
212      }
213
214      private boolean match(String s1, String s2)
215      {
216          char[] chars1 = s1.toCharArray();
217          char[] chars2 = s2.toCharArray();
218          for (int i = 0; i < chars1.length; i++)
219          {
220              char c = chars1[i];
221              if ((c != '?' && chars2[i] != '?' && chars2[i] != c))
222              {
223                  return false;
224              }
225          }
226          return true;
227      }
228
229      public rx(String filename) throws Exception
230      {
231          LineNumberReader lnr = new LineNumberReader(new FileReader(new File(filename)));
232          stringFromFile = lnr.readLine();
233          patternFromFile = lnr.readLine();
234          lnr.close();
235      }
236
237      public ArrayList splitByChar(String str, char token, boolean includeToken)
238      {
239          ArrayList arrayList = new ArrayList();
240          char[] chars = str.toCharArray();
241          StringBuffer sb = new StringBuffer();
242          for (int i = 0; i < chars.length; i++)
243          {
244              char aChar = chars[i];
245              if(aChar == token)
246              {
247                  String s = sb.toString();
248                  if(!s.equals(""))
249                  {
250                      arrayList.add(s);
251                  }
252                  sb = new StringBuffer();
253                  if(includeToken)
254                  {
255                      arrayList.add("" + token);
256                  }
257              }
258              else
259              {
260                  sb.append(aChar);
261              }
262
263          }
264          if(!sb.toString().equals(""))
265          {
266              arrayList.add(sb.toString());
267          }
268          return arrayList;
269      }
270  }

  1  program vgu2k6f;
  2  label _e;
  3  var
  4    wrd,pat,t: string;
  5    pa,pv,tp: byte;
  6    y: boolean;
  7
  8  function matchv(pat,wrd: string): boolean;
  9  var i: byte;
 10  begin
 11  matchv:=false;
 12  if pat='*' then
 13  begin
 14    matchv:=true;
 15    exit;
 16  end;
 17  if length(pat)<>length(wrd) then
 18    exit;
 19  for i:=1 to length(pat) do
 20  begin
 21    if pat[i]='?' then
 22      continue;
 23    if pat[i]<>wrd[i] then
 24      exit;
 25  end;
 26  matchv:=true;
 27  end;
 28
 29  function posi(pat,wrd: string): byte;
 30  var
 31    i,j,l: byte;
 32  begin
 33  posi:=0; l:=length(pat);
 34  if pos('?',pat)=0 then
 35  begin
 36    posi:=pos(pat,wrd);
 37    exit;
 38  end;
 39  if length(wrd)<l then
 40    exit;
 41  for i:=1 to length(wrd)-l+1 do
 42    if matchv(pat,copy(wrd,i,l)) then
 43      begin
 44        posi:=i;
 45        break;
 46      end;
 47  end;
 48
 49  begin
 50  Assign(input,'input.txt'); Assign(output,'output.txt');
 51  Reset(input); Rewrite(output);
 52  readln(wrd);
 53  readln(pat);
 54  if (pos('*',wrd)>0) or (pos('?',wrd)>0) then
 55  begin
 56    t:=pat;
 57    pat:=wrd;
 58    wrd:=t;
 59  end;
 60  y:=false;
 61  while pos('**',pat)>0 do
 62    delete(pat,pos('**',pat),1);
 63  while wrd<>'' do
 64  begin
 65    pa:=pos('*',pat);
 66    pv:=pos('?',pat);
 67    if (pa=0) and (pv=0) then
 68    begin
 69      if pat=wrd then
 70        y:=true;
 71      goto _e;
 72    end;
 73    if pv=1 then
 74    begin
 75      delete(wrd,1,1);
 76      delete(pat,1,1);
 77      continue;
 78    end;
 79    if pa>1 then
 80    begin
 81      t:=copy(pat,1,pa-1);
 82      if not matchv(t,copy(wrd,1,pa-1)) then
 83        goto _e;
 84      delete(wrd,1,pa-1);
 85      delete(pat,1,pa-1);
 86      continue;
 87    end;
 88    {the only left case is '*' at pat[1]}
 89    delete(pat,1,1);
 90    if length(pat)=0 then {pat was '*' so will match anything}
 91    begin
 92      y:=true;
 93      goto _e;
 94    end;
 95    pa:=pos('*',pat);
 96    if pa=0 then
 97    begin
 98      if matchv(pat,copy(wrd,length(wrd)-length(pat)+1,length(pat))) then
 99        y:=true;
100      goto _e;
101    end;
102    t:=copy(pat,1,pa-1);
103    tp:=posi(t,wrd);
104    if tp=0 then
105      goto _e;
106    delete(wrd,1,tp+length(t)-1);
107    delete(pat,1,pa-1);
108  end;
109  if matchv(pat,wrd) then
110    y:=true;
111  _e: if y then
112    writeln('YES')
113  else
114    writeln('NO');
115  Close(input); Close(output);
116  end.

let rec is_it_pattern lst =
  match lst with
  | []      -> false
  | '*' :: tl -> true
  | '?' :: tl -> true
  |  _  :: tl -> is_it_pattern tl
;;
let rec check pattern_word =
  match pattern_word with
  | ([], []) -> true
  | ([], w::wtl)  -> false
  | ('?' :: ptl, w :: wtl)-> check (ptl, wtl)
  | ('?' :: ptl, [])-> false
  | (('*' :: ptl as pattern), (w :: wtl as word))
  -> check (ptl, word) || check (pattern, wtl)
  | ('*' :: ptl, [])-> check (ptl, [])
  | ( p  :: ptl, w :: wtl)-> (p = w) && check (ptl, wtl)
  | ( p  :: ptl, [])-> false
;;
let input, output = open_in "input.txt", open_out "output.txt";;
let read_line () = Stream.npeek 255 (Stream.of_string (input_line input));;
let first, second  = read_line(), read_line();;
let pattern_word = if (is_it_pattern first) then (first, second) else (second, first);;
let _ = output_string output (if check (pattern_word) then "YES" else "NO");;

 1  #include <stdio.h>
 2  #include <string.h>
 3
 4  FILE *f;
 5  char s1[258], s2[258];
 6  int prov (int p1, int p2);
 7
 8  int prov (int p1, int p2)
 9  {
10    for (; s1[p1] != '\0' && s2[p2] != '\0';) {
11      if (s1[p1] == '?') {
12        p1++;
13        p2++;
14      }
15      else if (s1[p1] == '*') {
16        for (; s1[p1] == '*'; p1++);
17        int b;
18        for (; s2[p2] != '\0'; p2++) {
19          for (; s2[p2] != s1[p1] && s1[p1] != '?' && s2[p2] != '\0'; p2++);
20            if (s2[p2] == '\0' && s1[p1] != '\0')
21              return 0;
22            if (s2[p2] == '\0' && s1[p1] == '\0')
23              return 1;
24            if (prov (p1, p2))
25              return 1;
26        }
27      } else {
28        if (s1[p1] == s2[p2]) {
29          p1++;
30          p2++;
31        }
32        else
33          return 0;
34      }
35    }
36    if (s1[p1] == '\0' && s2[p2] == '\0')
37      return 1;
38    else
39      return 0;
40  }
41
42  int main ()
43  {
44    f = fopen ("input.txt", "r");
45    fgets (s1, 257, f);
46    fgets (s2, 257, f);
47    int b = prov (0, 0);
48    if (!b) {
49      char s[258];
50      strcpy (s, s1);
51      strcpy (s1, s2);
52      strcpy (s2, s);
53      b = prov (0, 0);
54    }
55    printf ("\n%s\n", (b) ? "YES" : "NO");
56  }