Pagini recente » Cod sursa (job #2147999) | Cod sursa (job #472153) | Cod sursa (job #2748798) | Cod sursa (job #1064782) | Cod sursa (job #796947)
Cod sursa(job #796947)
#include <iostream>
#include <fstream>
#include <string>
using namespace std;
void compute_t(string W, int T[]) {
int cnd = 0;
int pos = 2;
T[0] = -1;
T[1] = 0;
while(pos < W.length()) {
if( W[pos -1] == W[cnd]) {
cnd++;
T[pos] = cnd;
pos++;
} else if(cnd > 0)
cnd = T[cnd];
else {
T[pos] = 0;
pos++;
}
}
}
int main() {
ifstream in("strmatch.in");
string A, B;
in >> A >> B;
in.close();
int T[A.length()];
compute_t(A, T);
int n = 0, poz[1000];
int m = 0, i = 0;
while(m+i < B.length()) {
if(A[i] == B[m+i]) {
if(i == A.length() - 1) {
n++;
if(n <= 1000)
poz[n-1] = m;
m = m + i - T[i];
i = T[i] > -1 ? T[i] : 0;
}
else
i++;
} else {
m = m + i - T[i];
i = T[i] > -1 ? T[i] : 0;
}
}
ofstream out("strmatch.out");
out << n << endl;
int val = n < 1000 ? n: 1000;
for(i = 0; i < val; i++)
out << poz[i] << " ";
out.close();
return 0;
}