Small Shift-AND implementation. Allows wildcards. Works lowercase only with patterns up to 32 characters (uint32-bound, easily changed to 64-bit or bitvectors) http://en.wikipedia.org/wiki/Bitap_algorithm

gistfile1.cs

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Diagnostics;
using System.Threading.Tasks;

namespace ShiftAnd
{
    class Program
    {
        static void Main(string[] args)
        {
            var t = "bagsfgsdfsdfanas";
            var z = "sfg*ana";
            Console.WriteLine("Match at {0}.", ShiftAndWildcard(t, z));

            Console.ReadLine();
        }

        static int ShiftAndWildcard(string t, string z)
        {
            var parts = z.Split('*');
            var count = parts.Length;
            var start = 0;
            var firstMatch = -1;

            for (var i = 0; i < count; ++i)
            {
                start = ShiftAnd(t, parts[i], start);
                if (start == -1)
                    return -1;

                else if (i == 0)
                    firstMatch = start;
            }
            return firstMatch;
        }

        static int ShiftAndWithV(string t, string z, uint[] c, int start)
        {
            uint matchBit = (1u << (z.Length - 1));
            int len = t.Length;

            uint v = 0;
            int i;
            for (i = start; i < len && (v & matchBit) == 0; ++i)
            {
                v = ((v << 1) | 1u) & c[t[i] - 'a'];
            }
            return i == len && (v & matchBit) == 0 ? -1 : i - z.Length;
        }

        static int ShiftAnd(string t, string z, int start)
        {
            uint[] c = GenerateVectors(z);
            return ShiftAndWithV(t, z, c, start);
        }

        static uint[] GenerateVectors(string z)
        {
            uint[] c = new uint[26];
            for (byte i = 0; i < z.Length; ++i)
            {
                c[z[i] - 'a'] |= 1u << i;
            }
            return c;
        }
    }
}