Pagini recente » Cod sursa (job #76499) | Cod sursa (job #2090894) | Cod sursa (job #2077035) | Cod sursa (job #2280959) | Cod sursa (job #2088181)
#include<fstream>
#include<cstring>
using namespace std;
#define maxLength 2000001
#define threshold 1000
#define max(a,b) (a>b ? a : b)
int i, j, pi[maxLength];
char A[maxLength], B[maxLength];
void computePiFunction(char pattern[]) {
int k, patternLength = strlen(pattern);
pi[0] = -1;
k = -1;
for (i = 1; i < patternLength; ++i) {
while (k > -1 && pattern[k + 1] != pattern[i]) {
k = pi[k];
}
if (pattern[k + 1] == pattern[i]) {
k = k + 1;
}
pi[i] = k;
}
}
int main() {
ifstream inFile("strmatch.in");
ofstream outFile("strmatch.out");
inFile >> A >> B;
computePiFunction(A);
int lengthA = strlen(A), lengthB = strlen(B);
int k = -1, positions = 0, matches[1000];
for (i = 0; i < lengthB; ++i) {
while (k > -1 && A[k + 1] != B[i]) {
k = pi[k];
}
if (A[k + 1] == B[i]) {
k = k + 1;
}
if (k == lengthA - 1) {
if (positions < threshold) {
positions++;
matches[positions - 1] = i - k;
}
}
}
outFile << positions << "\n";
for (i = 0; i < positions; i++) {
outFile << matches[i] << " ";
}
inFile.close();
outFile.close();
return 0;
}