Pagini recente » Cod sursa (job #3142341) | Cod sursa (job #594149) | Cod sursa (job #2543000) | Cod sursa (job #2801911) | Cod sursa (job #2908498)
#include <fstream>
#include <vector>
#include <cstring>
#include <iostream>
using namespace std;
void buildPrefixVect(string substring, vector <int>& prefArray){
int sz = substring.size();
//cout << sz;
prefArray.resize(sz, 0);
int i = 0, j = 1;
while(i < sz && j < sz) {
if(substring[i] == substring[j]) {
prefArray[j] = i + 1;
i++;
} else {
if(i > 0){
i = prefArray[i - 1];
}
}
j++;
}
}
int main()
{
ifstream f("strmatch.in");
ofstream g("strmatch.out");
string substring, bigString;
f >> substring;
f >> bigString;
int matches = 0;
vector <int> startIndexes;
vector <int> prefArray;
buildPrefixVect(substring, prefArray);
/*
for(int i = 0; i < prefArray.size(); ++i) {
cout << prefArray[i] << " ";
}
*/
int subStringPos = 0;
int subStringSize = substring.size();
int bigStringSize = bigString.size();
for(int i = 0; i < bigStringSize; ++i) {
if(substring[subStringPos] == bigString[i]) {
subStringPos++;
//am terminat de parcurs substringul
if(subStringPos == subStringSize) {
matches++;
///plus 1 pt ca subStringPos = lungimea substringului
///substringul este indexat de la 0 -> deci subStringPos este inafara arrayului
if(matches < 1000) {
startIndexes.push_back(i - subStringPos + 1);
}
subStringPos = prefArray[subStringPos - 1];
}
} else {
if(subStringPos > 0)
subStringPos = prefArray[subStringPos - 1];
}
}
g << matches << "\n";
if(matches > 1000) {
matches = 1000;
}
for(int i = 0; i < matches; ++i) {
g << startIndexes[i] << " ";
}
f.close();
g.close();
return 0;
}