Pagini recente » Cod sursa (job #41682) | Cod sursa (job #219779)
Cod sursa(job #219779)
#include <stdio.h>
#include <string>
#include <queue>
#define nmax 2000001
using namespace std;
string w,s;
int T[nmax];
queue<int> sol;
void readuire()
{
char c;
freopen("strmatch.in","r",stdin);
c = getc(stdin);
while (c!='\n'){
w += c;
c = getc(stdin);
}
c = getc(stdin);
while (!feof(stdin)){
s += c;
c = getc(stdin);
}
fclose(stdin);
}
void compute_table(string w, int T[nmax])
{
// Compute the Skip Table
int pos = 2,cnd = 0,l=w.length();
T[0] = -1;
T[1] = 0;
while (pos<l){
// case 1 : the substring continues
if (w[pos-1] == w[cnd]){
T[pos] = T[pos-1] + 1;
pos++;
cnd++;
}
else
// case 2 : Substring doesn't continue, but we might have a
// smaller prefix
if (cnd > 0)
cnd = T[cnd];
else{
// case 3 : hopeless case ..
T[pos] = 0;
pos ++;
}
}
}
int KMP(string s, string w)
{
int pos = 0, ls = s.length(), lw = w.length(), numb = 0;
int cur = 0;
while (pos < ls-lw+1 && numb < 1000){
while (w[cur] == s[pos+cur] && cur < lw)
cur ++;
if (cur == lw){
sol.push(pos);
cur = 0;
pos += 1;
numb++;
}
else{
pos += cur - T[cur];
cur = cur > 0 ?T[cur] : 0;
}
}
return numb;
}
void scriere(int nr)
{
freopen("strmatch.out","w",stdout);
printf("%d\n",nr);
while ( !sol.empty()){
printf("%d ",sol.front());
sol.pop();
}
fclose(stdout);
}
int main()
{
readuire();
compute_table(w,T);
scriere(KMP(s,w));
return 0;
}