Pagini recente » Cod sursa (job #2048453) | Cod sursa (job #1154432) | Cod sursa (job #2170032) | Cod sursa (job #2834067) | Cod sursa (job #3242048)
#include <iostream>
#include <vector>
#include <fstream>
#include <string.h>
#define MAX 2000000
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
int *createSubPatterns(string p){
int *lps = (int*) malloc(p.length() * sizeof(int));
int i = 1, j = 0;
while(i < p.length()){
if(p[i] == p[j]){
j++;
lps[i] = j;
i++;
}
else{
if(j > 0){
j = lps[j-1];
}
else{
lps[i] = 0;
i++;
}
}
}
return lps;
}
int main(){
string p, s;
vector<int> pos(1001);
getline(in, p);
getline(in, s);
int* lps = createSubPatterns(p);
/*
for(int i = 0; i<p.length(); i++)
cout << lps[i] << ", ";
cout << endl;
*/
int j = 0;
int matches = 0;
for(int i = 0; i<s.length(); i++){
if(j == p.length()){
pos[matches++] = i;
j = lps[j-1]; // lps[j];
if(matches == 1000)
break;
}
if(s[i] == p[j]) j++;
else if(j > 0){
j = lps[j-1];
i--;
}
}
out << matches << endl;
for(int i = 0; i<matches; i++)
out << pos[i] - p.length() << " ";
}