Pagini recente » Cod sursa (job #1819009) | Cod sursa (job #1546454) | Cod sursa (job #1275629) | Cod sursa (job #2895303) | Cod sursa (job #2088190)
#include<fstream>
#include<cstring>
using namespace std;
#define maxLength 2000001
#define threshold 1000
#define min(a,b) (a < b ? a : b)
int i, j, pi[maxLength], matches[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;
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) {
matches[positions++] = i - k;
}
}
outFile << positions << "\n";
for (i = 0; i < min(threshold, positions); i++) {
outFile << matches[i] << " ";
}
inFile.close();
outFile.close();
return 0;
}