Pagini recente » Cod sursa (job #713975) | Cod sursa (job #716172) | Cod sursa (job #1587143) | Cod sursa (job #694022) | Cod sursa (job #922533)
Cod sursa(job #922533)
#include <fstream>
#include <string>
#include <vector>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
string A, B;
int T[2000001];
vector<int> sol;
int main()
{
fin>>A>>B;
for(int i=1;i<A.length();i++)
{
if(A[ T[i-1] ] == A[i])
T[i] = 1 + T[i-1];
else if(A[i]==A[0])
T[i] = 1;
}
int k=0;
for(int i=0;i<B.length();i++)
{
if(A[k] == B[i])
{
k++;
if(k == A.size())
{
sol.push_back(i);
k = T[k-1];
}
}
else
{
while(k && A[k]!=B[i])
k = T[k];
if(A[k]==B[i])
{
k++;
if(k == A.size())
{
sol.push_back(i);
k = T[k-1];
}
}
}
}
fout<<sol.size()<<'\n';
for(unsigned int i=0;i<sol.size();i++)
fout<<sol[i]-A.size()+1<<' ';
fin.close();
fout.close();
return 0;
}