Pagini recente » Cod sursa (job #1119509) | Cod sursa (job #914896) | Cod sursa (job #879217) | Cod sursa (job #430936) | Cod sursa (job #2794835)
///Solutie - KMP
#include <bits/stdc++.h>
using namespace std;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
const int LIM = 2000005;
vector <int> sol;
int lps[LIM];
string a, b;
int na, nb;
int main (){
fin>>a; na = a.size(); a = " " + a;
fin>>b; nb = b.size(); b = " " + b;
if(na > nb){fout<<0; return 0;}
lps[0]=0;
for(int i=2, len=0; i <= na; i++){
while(len != 0 && a[i] != a[len+1])
len = lps[len];
if(a[i] == a[len+1])
len++;
lps[i] = len;
}
for(int i=1, len=0; i <= nb; i++){
while(len != 0 && b[i] != a[len+1])
len = lps[len];
if(b[i] == a[len+1])
len++;
if(len == na)
sol.push_back(i-na);
}
fout<<sol.size()<<"\n"; int go = min(1000, (int)sol.size());
for(int i=0; i<go; i++)
fout<<sol[i]<<" ";
return 0;
}