Pagini recente » Cod sursa (job #1731255) | Cod sursa (job #135095) | Cod sursa (job #1888084) | Cod sursa (job #235040) | Cod sursa (job #1736419)
#include <iostream>
#include <string>
#include <vector>
#include <fstream>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
const int MAXN = 2000000;
string A, B;
int nA, nB, T[MAXN+1], solSize;
vector <int> sol;
void kmp(string A, string B)
{
for(int i = 1; i < nA; i++)
{
int j = T[i-1];
while(A[j] != A[i])
{
j = T[j-1];
if(j == 0)
break;
}
if(j == 0)
{
if(A[0] == A[i])
T[i] = 1;
}
else
T[i] = j + 1;
}
int i = 0, j = 0, p = 0;
while(i < nB)
{
p = i - j;
while(B[i] == A[j] && i < nB && j < nA)
i++, j++;
if(j == nA)
sol.push_back(p);
if(p == i)
{
i++;
j = 0;
}
else
if(j != 0)
j = T[j-1];
}
}
int main()
{
in>>A>>B;
nA = A.length();
nB = B.length();
kmp(A,B);
out<<sol.size()<<endl;
solSize = min(1000,(int)sol.size());
for(int i = 0; i < solSize; i++)
out<<sol[i]<<' ';
return 0;
}