1using System;
2using System.Collections.Generic;
3using System.Text;
4
5namespace StringFinder
6{
7    class Program
8    {
9        static void Main(string[] args)
10        {
11            StringFinder sf = new StringFinder("Hello");
12
13            int index = sf.FindString("This is a String Finder's Hello World Program");
14
15            Console.WriteLine(index);
16        }
17
18        class StringFinder
19        {
20            Pattern _pattern;
21            int _startIndex;
22            public StringFinder(string pattern)
23            {
24                _pattern = new Pattern(pattern);
25                _startIndex = pattern.Length - 1;
26            }
27
28            public int FindString(string s)
29            {
30                int k = 0;
31                int i = _startIndex;
32
33                while (true)
34                {
35                    if (s[i - k] == _pattern.GetChar(k))
36                    {
37                        k++;
38
39                        if (k == _pattern.GetPatternLength())
40                        {
41                            return i;
42                        }
43                    }
44                    else
45                    {
46                        int temp1 = _pattern[s[i - k]] - k;
47                        int temp2 = _pattern[s[i]];
48
49                        i += temp1 > temp2 ? temp1 : temp2;
50
51                        k = 0;
52
53                        if (i > s.Length - 1)
54                        {
55                            return -1;
56                        }
57                    }
58                }
59            }
60        }
61
62        class Pattern
63        {
64            int[] _pattern;
65            string _chars;
66
67            public Pattern(string pattern)
68            {
69                _chars = pattern;
70                _pattern = new int[(int)Char.MaxValue];
71
72                for (int i = 0; i < _pattern.Length; i++)
73                {
74                    _pattern[i] = pattern.Length;
75                }
76
77                for (int i = 0; i < pattern.Length; i++)
78                {
79                    this[pattern[i]] = pattern.Length - i - 1;
80                }
81            }
82
83            public char GetChar(int index)
84            {
85                int i = _chars.Length - index - 1;
86                return _chars[i];
87            }
88
89            public int GetPatternLength()
90            {
91                return _chars.Length;
92            }
93
94            public int this[char c]
95            {
96                set
97                {
98                    _pattern[(int)c] = value;
99                }
100                get
101                {
102                    return _pattern[(int)c];
103                }
104            }
105        }
106    }
107}