Pagini recente » Cod sursa (job #1521031) | Cod sursa (job #2389327) | Cod sursa (job #2457499) | Cod sursa (job #1675175) | Cod sursa (job #3301761)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
string A, B;
vector<int> prefix_function(const string &P)
{
vector<int> prefix(P.size());
prefix[0] = 0;
int k = 0;
for(int i = 1; i < P.size(); i++)
{
while(k > 0 && P[k] != P[i])
k = prefix[k - 1];
k += (P[k] == P[i]);
prefix[i] = k;
}
return prefix;
}
int main()
{
fin >> A >> B;
string S = A + '*' + B;
vector<int> prefix = prefix_function(S), positions;
for(int i = A.size() + 1; i < S.size() && positions.size() <= 1000; i++)
if(prefix[i] == A.size())
positions.push_back(i - 2 * A.size());
fout << positions.size() << "\n";
for(int poz : positions)
fout << poz << " ";
fin.close();
fout.close();
return 0;
}