}

}

classSolution {

funstrStr(haystack:String,needle:String):Int {

if(needle.length> haystack.length)return-1

val q=101

val d=256

var needleHash=0

var hayHash=0

var hash=1

for (iin0..needle.lastIndex)

hash= (hash* d)% q

for(iin0..needle.lastIndex) {

needleHash= (d* needleHash+ (needle[i]-'a'))% q

hayHash= (d* hayHash+ (haystack[i]-'a'))% q

}

for(iin0..(haystack.length- needle.length)) {

if(hayHash== needleHash) {

for(jin0..needle.lastIndex) {

if(haystack[i+ j]!= needle[j])

if(j== needle.lastIndex)

return i

}

}

if(i== haystack.length- needle.length)

hayHash= (d* hayHash- ((haystack[i]-'a')* hash)+ (haystack[i+ needle.length]-'a'))% q

if(hayHash<0)

hayHash+= q

}

}

}