Pagini recente » Cod sursa (job #2000299) | Cod sursa (job #2273054) | Cod sursa (job #2078619) | Cod sursa (job #1610670) | Cod sursa (job #2000583)
#include <fstream>
#include <string>
#include <vector>
#include <iterator>
using namespace std;
int n, m, s=0;
void pattern(string &A, int* p, int i, int j) {
while (i < n) {
if (A[i] == A[j]) {
p[i] = j + 1;
i++;j++;
}
else if (j == 0) {
p[i] = p[j];
i++;
}
else j = p[j - 1];
}
}
void compare(string &A, string &B, int* p, int i, int j, vector<int>& lista) {
while (j < m) {
if (A[i] == B[j]) {
if (i == n - 1) {
if (s<1000)lista.push_back(j - n + 1);
s++;
i = p[i];j++;
}
else { i++;j++; }
}
else if (i != 0) i = p[i - 1];
else j++;
}
}
int main(){
ifstream in("strmatch.in");
string A,B;
in >> A >> B;
n = A.length();
int* p = new int[n];
p[0] = 0;
pattern(A,p,1,0);
vector<int>lista;
m = B.length();
compare(A, B, p, 0, 0,lista);
ofstream out("strmatch.out");
out << s <<"\n";
for (vector<int>::iterator it=lista.begin();it != lista.end();it++)
out << *it<<" ";
}