Pagini recente » Cod sursa (job #2547637) | Cod sursa (job #3277731) | Cod sursa (job #2868697) | Cod sursa (job #1428881) | Cod sursa (job #2891108)
#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;
}
}
}
}
}
void sol(vector<int> &theResArray, int sizeOfFirstArray, int sizeOfSecondArray, int &sizeOfRes)
{
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(sizeOfRes < 1000)
{
theResArray.push_back(i - sizeOfFirstArray);
++sizeOfRes;
}
else
++sizeOfRes;
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;
}
}
}
int main()
{
vector<int> theResArray;
fin.getline(theFirstArray, 2000001);
fin.getline(theSecondArray, 2000001);
int sizeOfFirstArray = strlen(theFirstArray);
int sizeOfSecondArray = strlen(theSecondArray);
preProcessing(theFirstArray, sizeOfFirstArray);
int sizeOfRes = 0;
sol(theResArray, sizeOfFirstArray, sizeOfSecondArray,sizeOfRes);
fout<<sizeOfRes<<'\n';
for(int i = 0; i < min(sizeOfRes , 1000); i++)
{
fout<<theResArray[i]<<" ";
}
return 0;
}