Pagini recente » Cod sursa (job #2224310) | Cod sursa (job #527536) | Cod sursa (job #2767713) | Cod sursa (job #1282965) | Cod sursa (job #878143)
Cod sursa(job #878143)
#include <cstdio>
#include <iostream>
#include <string>
#include <vector>
#include <cstdlib>
#include <cstring>
using namespace std;
void redirectInput(const char *in, const char *out)
{
freopen(in, "r", stdin);
freopen(out, "w", stdout);
}
void printVector(vector<int> &v, int size)
{
for(int i = 0; i < size; ++i)
{
printf("%d ", v[i]);
}
printf("\n");
}
void buildMatchTable(vector<int> &T, char *a, int n)
{
T.resize(n, 0);
T[0] = -1;
T[1] = 0;
int k = 0;
int i = 2;
while(i < n)
{
if(a[i - 1] == a[k])
{
++k, T[i] = k, ++i;
} else if(k > 0)
{
k = T[k];
} else
{
T[i] = 0;
++i;
}
}
}
void KMP(char *a, char *b, int n, int m, vector<int> &T, vector<int> &matches)
{
int s = 0;//start of possible match
int p = 0;//number of chars matching so far
while( s + p < m )
{
if(b[s + p] == a[p])
{
if(p == n - 1)
{
matches.push_back(s);
s += p - T[p];
p = (T[p] != -1) ? T[p] : 0;
} else
{
++p;
}
} else
{
s += p - T[p];
if(T[p] != -1)
{
p = T[p];
} else
{
p = 0;
}
}
}
}
void printSolution(vector<int> &matches)
{
cout << matches.size() << endl;
int n = (matches.size() < 1000) ? matches.size() : 1000;
for(int i = 0; i < n; ++i)
{
cout << matches[i] << " ";
}
cout << endl;
}
void solve()
{
char *a = (char*) calloc(2000000, sizeof(char));
char *b = (char*) calloc(2000000, sizeof(char));
scanf("%s %s", a, b);
int n = strlen(a);
int m = strlen(b);
vector<int> T;
vector<int> matches;
buildMatchTable(T, a, n);
KMP(a, b, n, m, T, matches);
printSolution(matches);
}
int main(int argc, char *argv[])
{
if(argc == 2)
{
redirectInput(argv[1],"strmatch.out");
} else
{
redirectInput("strmatch.in","strmatch.out");
}
solve();
return 0;
}