Pagini recente » Cod sursa (job #1810416) | Cod sursa (job #2851826) | Cod sursa (job #30747) | Cod sursa (job #1225272) | Cod sursa (job #1735440)
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
const int MAXN = 2000000;
string A, B;
int table[MAXN+1], nA, nB, solSize;
vector <int> sol;
void buildTable()
{
for(int i = 1; i < nA; i++)
{
int left = 0, right = i, m = 0;
for(int j = i; j >= 1; j--)
if(A.substr(0,j) == A.substr(i-j+1,j))
{
table[i] = j;
break;
}
}
/*for(int i = 0; i < nA; i++)
cout<<table[i]<<' ';
cout<<endl;*/
}
void match(string A, string B)
{
if(nA > nB)
{
cout<<0;
return;
}
int i = 0;
while(i < nB && nA <= nB - i)
{
int j = 0;
while(B[i+j] == A[j] && j < nA)
{
//cout<<i<<' '<<j<<' '<<B[i+j]<<' '<<A[j]<<endl;
j++;
}
if(j == nA)
{
//cout<<i<<endl;
sol.push_back(i);
}
if(table[j-1] != 0)
i=i+j-table[j-1];
else
i++;
}
}
int main()
{
in>>A>>B;
nA = A.length();
nB = B.length();
buildTable();
match(A,B);
if(sol.size() > 1000)
solSize = 1000;
else
solSize = sol.size();
out<<solSize<<endl;
for(int i = 0; i < solSize; i++)
out<<sol[i]<<' ';
return 0;
}