Pagini recente » Cod sursa (job #2729688) | Cod sursa (job #2775917) | Cod sursa (job #944657) | Cod sursa (job #825139) | Cod sursa (job #3142136)
#include <fstream>
#include <string.h>
#include <vector>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
int n, m, T[10005];
char S[10005], W[10005];
vector<int> V;
void Prep(int m, char W[], int T[])
{
int lg = 0;
int i = 1;
while(i < m)
{
if(W[i] == W[lg]){
lg ++;
T[i ++] = lg;
}
else{
if(lg)
lg = T[lg - 1];
else
T[i ++] = 0;
}
}
}
void KMPSearch(char S[], char W[])
{
n = strlen(S);
m = strlen(W);
Prep(m, W, T);
int i, j; i = j = 0;
while((n - i) >= (m - j))
{
if(S[i] == W[j])
j ++, i ++;
if(j == m){
if(V.size() < 1000)
V.push_back(i - j);
j = T[j - 1];
}
else if(i < n && W[j] != S[i]){
if(j)
j = T[j - 1];
else
i ++;
}
}
}
int main()
{
f >> W >> S;
KMPSearch(S, W);
g << V.size() << '\n';
for(int i = 0; i < V.size(); i ++)
g << V[i] << " ";
return 0;
}