Pagini recente » Cod sursa (job #1353270) | Cod sursa (job #2634290) | Cod sursa (job #1055343) | Cod sursa (job #2363616) | Cod sursa (job #2891107)
#include <iostream>
#include<cstring>
#include<fstream>
#include<vector>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char theFirstArray[2000001];
char theSecondArray[2000001];
int dpOfFirst[2000001];
// first array is the array which you check if it's in the second array
void preProcessing(char theArray[], int sizeOfArray){
dpOfFirst[0] = 0;
for(int i = 1; i < sizeOfArray; i++){
int lastPos = dpOfFirst[i - 1];
if(lastPos == 0){
// case AA
if(theArray[i] == theArray[lastPos]){
dpOfFirst[i] = 1;
}
// case AB
else{
dpOfFirst[i] = 0;
}
}
else{ // you found something that is equal to this
if(theArray[i] == theArray[lastPos]){
dpOfFirst[i] = dpOfFirst[i - 1] + 1;
}
else{ // the case like ABXABXA
// with dpOfFirst: 0001231
int aux = lastPos;
while(theArray[aux] != theArray[i] && aux != 0){
// you check the letters
aux = dpOfFirst[aux];
}
if(theArray[aux] == theArray[i]){
dpOfFirst[i] = dpOfFirst[aux] + 1;
}
else{
dpOfFirst[i] = 0;
}
}
}
}
}
vector<int> theResArray;
int main()
{
fin.getline(theFirstArray, 2000001);
fin.getline(theSecondArray, 2000001);
int sizeOfFirstArray = strlen(theFirstArray);
int sizeOfSecondArray = strlen(theSecondArray);
preProcessing(theFirstArray, sizeOfFirstArray);
int j = 0;
int i = 0;
// i - the index in the secondArray which you need to search in
// j - the index in the firstArray which was pre-processed
while(i < sizeOfSecondArray){
if(theFirstArray[j] == theSecondArray[i]){
++j;
++i;
}
if( j == sizeOfFirstArray){
if(theResArray.size() < 1000)
theResArray.push_back(i - sizeOfFirstArray);
else
i = sizeOfSecondArray + 1;
j = dpOfFirst[j - 1];
// so that you don't always start at 0
}
if (i < sizeOfSecondArray&& theFirstArray[j] != theSecondArray[i]){
if(j != 0)
j = dpOfFirst[j - 1];
else
i = i + 1;
}
}
fout<<theResArray.size()<<'\n';
int sizeOfRes = theResArray.size();
for(int i = 0; i < min(sizeOfRes , 1000); i++){
fout<<theResArray[i]<<" ";
}
return 0;
}