Pagini recente » Cod sursa (job #2463107) | Cod sursa (job #2999102) | Cod sursa (job #2633132) | Cod sursa (job #3206285) | Cod sursa (job #1220604)
#include<vector>
#include<fstream>
#include<string.h>
using namespace std;
#define FIN "strmatch.in"
#define FOUT "strmatch.out"
#define MAX 2000002
ifstream f(FIN);
ofstream g(FOUT);
char A[MAX];
char B[MAX];
int table[125]; //bad mismatch table
vector<int> solution;
int count;
void read()
{
f.getline(A, MAX);
f.getline(B, MAX);
}
int compare(int index, int length)
{
for(int i=0;i<length;i++)
{
if(A[i] != B[index + i])
return 1;
}
return 0;
}
void solve()
{
int length = strlen(A);
int strlength = strlen(B);
//preprocessing
//ASCII intervals for numbers and letters
//48 - 57 , 65-90 , 97 - 122
for(int i=1; i < length -1; i++)
{
table[(int)A[i]] = length - i - 1;
}
//the last letter
if(table[(int)A[length]] == 0)
table[(int)A[length]] = length;
//comparation
int index = 0;
while(index + length <= strlength)
{
if(compare(index, length) == 0)
{
count++;
solution.push_back(index);
index++;
}
else
{
if(table[B[index + length - 1]] == 0)
{
index += length;
}
else
{
index += table[B[index + length - 1]];
}
}
}
}
void write()
{
g << count << endl;
for(vector<int>::iterator it = solution.begin(); it!=solution.end(); it++)
g << *it << " ";
}
int main()
{
read();
solve();
write();
return 0;
}