Pagini recente » Cod sursa (job #1237118) | Cod sursa (job #584701) | Cod sursa (job #1043045) | Cod sursa (job #1434976) | Cod sursa (job #2833813)
#include <bits/stdc++.h>
using namespace std;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
const int DIM = 2e6 + 50;
int sol, st, dr;
int len, kmp[ 2 * DIM];
string a, b;
int main (){
fin>>b>>a;
a = " " + b + "$" + a;
kmp[1] = 0;
for(int i=2; i < (int)a.size(); i++){
len = kmp[i-1];
while(a[len+1] != a[i] && len > 0)
len = kmp[len];
kmp[i] = len + (a[len+1] == a[i]);
}
for(int i=1; i < (int)a.size(); i++)
if(kmp[i] == (int)b.size()){
sol++;
if(sol == 1){
st = i - (int)b.size() - 2 - (int)b.size() + 1;
dr = i - (int)b.size() - 2;
}
}
fout<<sol<<"\n"<<st<<" "<<dr;
return 0;
}