Pagini recente » Cod sursa (job #944435) | Cod sursa (job #2231629) | Cod sursa (job #1090761) | Cod sursa (job #1523127) | Cod sursa (job #2759312)
#include <fstream>
#include <string>
#include <vector>
using namespace std;
int main(){
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
string A, B;
cin >> A;
cin >> B;
vector<int> lps(A.length(), 0);
for(int i = 1, len = 0; i < A.length();){
if(A[i] == A[len]){
++len;
lps[i] = len;
++i;
}
else if(len > 0)
len = lps[len - 1];
else{
lps[i] = 0;
++i;
}
}
vector<int> result;
for(int i = 0, j = 0; i < B.length() && result.size() < 1000;){
if(A[j] == B[i]){
++i;
++j;
}
if(j == A.length()){
result.push_back(i - j);
j = lps[j - 1];
}
else if(i < B.length() && A[j] != B[i]){
if(j > 0)
j = lps[j - 1];
else ++i;
}
}
cout << result.size() << "\n";
for(auto pos : result)
cout << pos << " ";
cin.close();
cout.close();
return 0;
}